Sarah Ahmadian

PhD. Candidate

Local-Search based Approximation Algorithms for Mobile Facility Location Problem

  Computer Engineering Department, Floor 4, Kharazmi Hall
  Wednesday, 30 December 2015
  16:45 - 17:45

Abstract

The first part of the talk includes an introduction to approximation algorithm and facility location problems. One of the most-studied versions of the facility location problem is k-median problem in which we are given a set of clients located in a common metric space G=(V,c), and the goal is to open k centers (in V) and move each client to the closest center so that the total movement costs of clients is minimized. I will explain how a simple local- search based algorithm with swap moves will achieve an approximation guarantee of (3+\epsilon).

In the second part of the talk, we will focus on the mobile facility location (MFL) problem. We are given a set of facilities and clients located in a common metric space G = (V, c). The goal is to move each facility from its initial location to a destination (in V ) and assign each client to the destination of some facility so as to minimize the sum of the movement costs of the facilities and the client-assignment costs. We give the first local-search based approximation algorithm for this problem and achieve the best-known approximation guarantee. Our main result is (3 +\epsilon )-approximation for this problem for any constant \epsilon> 0 using local search. The previous best guarantee for MFL was an 8-approximation algorithm due to Friggstad and Salavatipour based on LP-rounding.

Bio

I joined the Department of Combinatorics and Optimization at the University of Waterloo in September 2008 after completing my Bachelor of Science in Computer Engineering at Sharif University of Technology. After finishing my Master’s, I worked for a start-up company for two years. Then, I started my PhD in May 2012 under supervision of Prof. Swamy. For research, I mostly think about algorithms. My research interests include combinatorial optimization, approximation algorithms, algorithmic game theory, and online algorithms.