Ahmadian, Sara ;
Behsaz, Babak ;
Friggstad, Zachary ;
Jorati, Amin ;
Salavatipour, Mohammad R. ;
Swamy, Chaitanya
Approximation Algorithms for MinimumLoad kFacility Location
Abstract
We consider a facilitylocation problem that abstracts settings where the cost of serving the clients assigned to a facility is incurred by the facility. Formally, we consider the minimumload kfacility location (MLkFL) problem, which is defined as follows. We have a set F of facilities, a set C of clients, and an integer k > 0. Assigning client j to a facility f incurs a connection cost d(f, j). The goal is to open a set F' of k facilities, and assign each client j to a facility f(j) in F' so as to minimize maximum, over all facilities in F', of the sum of distances of clients j assigned to F' to F'. We call
this sum the load of facility f. This problem was studied under the name of minmax star cover in [6, 2], who (among other results) gave bicriteria approximation algorithms for MLkFL for when F = C. MLkFL is rather poorly understood, and only an O(k)approximation is currently known for MLkFL, even for line metrics. Our main result is the first polynomial time approximation scheme (PTAS) for MLkFL on line metrics (note that no nontrivial true approximation of any kind was known for this metric). Complementing this, we prove that MLkFL is strongly NPhard on line metrics. We also devise a quasiPTAS for MLkFL on tree metrics. MLkFL turns out to be surprisingly challenging even on line metrics, and resilient to attack by the variety of techniques that have been successfully applied to facilitylocation problems. For instance, we show that: (a) even a configurationstyle LPrelaxation has a bad integrality gap; and (b) a multiswap kmedian style localsearch heuristic has a bad locality gap. Thus, we need to devise various novel techniques to attack MLkFL. Our PTAS for line metrics consists of two main ingredients. First, we prove that there always exists a nearoptimal solution possessing some nice structural properties. A novel aspect of this proof is that we first move to a mixedinteger LP (MILP) encoding the problem, and argue that a MILPsolution minimizing a certain potential function possesses the desired structure, and then use a rounding algorithm for the generalizedassignment problem to "transfer" this structure to the rounded integer solution. Complementing this, we show that these structural properties enable one to find such a structured solution via dynamic programming.
BibTeX  Entry
@InProceedings{ahmadian_et_al:LIPIcs:2014:4715,
author = {Sara Ahmadian and Babak Behsaz and Zachary Friggstad and Amin Jorati and Mohammad R. Salavatipour and Chaitanya Swamy},
title = {{Approximation Algorithms for MinimumLoad kFacility Location}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
pages = {1733},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897743},
ISSN = {18688969},
year = {2014},
volume = {28},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4715},
URN = {urn:nbn:de:0030drops47154},
doi = {10.4230/LIPIcs.APPROXRANDOM.2014.17},
annote = {Keywords: approximation algorithms, minmax star cover, facility location, line metrics}
}
04.09.2014
Keywords: 

approximation algorithms, minmax star cover, facility location, line metrics 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Issue date: 

2014 
Date of publication: 

04.09.2014 