Pilipczuk, Michal ;
van Leeuwen, Erik Jan ;
Wiese, Andreas
QuasiPolynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs
Abstract
We consider two optimization problems in planar graphs. In {Maximum Weight Independent Set of Objects} we are given a graph G and a family D of {objects}, each being a connected subgraph of G with a prescribed weight, and the task is to find a maximumweight subfamily of D consisting of pairwise disjoint objects. In {Minimum Weight Distance Set Cover} we are given an edgeweighted graph G, two sets D,C of vertices of G, where vertices of D have prescribed weights, and a nonnegative radius r. The task is to find a minimumweight subset of D such that every vertex of C is at distance at most r from some selected vertex. Via simple reductions, these two problems generalize a number of geometric optimization tasks, notably {Maximum Weight Independent Set} for polygons in the plane and {Weighted Geometric Set Cover} for unit disks and unit squares. We present {quasipolynomial time approximation schemes} (QPTASs) for both of the above problems in planar graphs: given an accuracy parameter epsilon>0 we can compute a solution whose weight is within multiplicative factor of (1+epsilon) from the optimum in time 2^{poly(1/epsilon,log D)}* n^{O(1)}, where n is the number of vertices of the input graph. Our main technical contribution is to transfer the techniques used for recursive approximation schemes for geometric problems due to Adamaszek, HarPeled, and Wiese [Adamaszek and Wiese, 2013; Adamaszek and Wiese, 2014; Sariel HarPeled, 2014] to the setting of planar graphs. In particular, this yields a purely combinatorial viewpoint on these methods.
BibTeX  Entry
@InProceedings{pilipczuk_et_al:LIPIcs:2018:9528,
author = {Michal Pilipczuk and Erik Jan van Leeuwen and Andreas Wiese},
title = {{QuasiPolynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {65:165:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9528},
URN = {urn:nbn:de:0030drops95282},
doi = {10.4230/LIPIcs.ESA.2018.65},
annote = {Keywords: QPTAS, planar graphs, Voronoi diagram}
}
14.08.2018
Keywords: 

QPTAS, planar graphs, Voronoi diagram 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

14.08.2018 