Abstract
We consider the kMedian problem on planar graphs: given an edgeweighted planar graph G, a set of clients C subseteq V(G), a set of facilities F subseteq V(G), and an integer parameter k, the task is to find a set of at most k facilities whose opening minimizes the total connection cost of clients, where each client contributes to the cost with the distance to the closest open facility. We give two new approximation schemes for this problem:
 FPT Approximation Scheme: for any epsilon>0, in time 2^{O(k epsilon^{3} log (k epsilon^{1}))}* n^O(1) we can compute a solution that has connection cost at most (1+epsilon) times the optimum, with high probability.
 Efficient Bicriteria Approximation Scheme: for any epsilon>0, in time 2^{O(epsilon^{5} log (epsilon^{1}))}* n^O(1) we can compute a set of at most (1+epsilon)k facilities whose opening yields connection cost at most (1+epsilon) times the optimum connection cost for opening at most k facilities, with high probability.
As a direct corollary of the second result we obtain an EPTAS for Uniform Facility Location on planar graphs, with same running time.
Our main technical tool is a new construction of a "coreset for facilities" for kMedian in planar graphs: we show that in polynomial time one can compute a subset of facilities F_0 subseteq F of size k * (log n/epsilon)^O(epsilon^{3}) with a guarantee that there is a (1+epsilon)approximate solution contained in F_0.
BibTeX  Entry
@InProceedings{cohenaddad_et_al:LIPIcs:2019:11154,
author = {Vincent CohenAddad and Marcin Pilipczuk and Michal Pilipczuk},
title = {{Efficient Approximation Schemes for UniformCost Clustering Problems in Planar Graphs}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {33:133:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11154},
URN = {urn:nbn:de:0030drops111543},
doi = {10.4230/LIPIcs.ESA.2019.33},
annote = {Keywords: kMedian, Facility Location, Planar Graphs, Approximation Scheme}
}
Keywords: 

kMedian, Facility Location, Planar Graphs, Approximation Scheme 
Collection: 

27th Annual European Symposium on Algorithms (ESA 2019) 
Issue Date: 

2019 
Date of publication: 

06.09.2019 