TY - GEN

T1 - Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs

AU - Pilipczuk, Michał

AU - Van Leeuwen, Erik Jan

AU - Wiese, Andreas

N1 - Publisher Copyright:
© Michał Pilipczuk, Erik Jan van Leeuwen, and Andreas Wiese.

PY - 2018/8/1

Y1 - 2018/8/1

N2 - 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 ϵ > 0 we can compute a solution whose weight is within multiplicative factor of (1 + ϵ) from the optimum in time 2poly(1/ϵ,log|D|) · no(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 [1, 2, 4] to the setting of planar graphs. In particular, this yields a purely combinatorial viewpoint on these methods.

AB - 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 ϵ > 0 we can compute a solution whose weight is within multiplicative factor of (1 + ϵ) from the optimum in time 2poly(1/ϵ,log|D|) · no(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 [1, 2, 4] to the setting of planar graphs. In particular, this yields a purely combinatorial viewpoint on these methods.

KW - Planar graphs

KW - QPTAS

KW - Voronoi diagram

UR - http://www.scopus.com/inward/record.url?scp=85052529669&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2018.65

DO - 10.4230/LIPIcs.ESA.2018.65

M3 - Conference contribution

AN - SCOPUS:85052529669

SN - 9783959770811

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 26th European Symposium on Algorithms, ESA 2018

A2 - Bast, Hannah

A2 - Herman, Grzegorz

A2 - Azar, Yossi

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 26th European Symposium on Algorithms, ESA 2018

Y2 - 20 August 2018 through 22 August 2018

ER -