License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.65
URN: urn:nbn:de:0030-drops-95282
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9528/
Go to the corresponding LIPIcs Volume Portal

Pilipczuk, Michal ; van Leeuwen, Erik Jan ; Wiese, Andreas

Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs

pdf-format:
LIPIcs-ESA-2018-65.pdf (0.7 MB)

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 maximum-weight subfamily of D consisting of pairwise disjoint objects. In {Minimum Weight Distance Set Cover} we are given an edge-weighted 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 minimum-weight 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 {quasi-polynomial 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, Har-Peled, and Wiese [Adamaszek and Wiese, 2013; Adamaszek and Wiese, 2014; Sariel Har-Peled, 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 =	{{Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{65:1--65:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Yossi Azar and Hannah Bast and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9528},
  URN =		{urn:nbn:de:0030-drops-95282},
  doi =		{10.4230/LIPIcs.ESA.2018.65},
  annote =	{Keywords: QPTAS, planar graphs, Voronoi diagram}
}

Keywords: QPTAS, planar graphs, Voronoi diagram
Collection: 26th Annual European Symposium on Algorithms (ESA 2018)
Issue Date: 2018
Date of publication: 14.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI