TY - JOUR
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:
© 2020, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2020/6/1
Y1 - 2020/6/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 a graph G in which the edges might have different lengths, 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 2 poly ( 1 / ϵ , log | D | )· nO ( 1 ), where n is the number of vertices of the input graph. We note that a QPTAS for Maximum Weight Independent Set of Objects would follow from existing work. However, our main contribution is to provide a unified framework that works for both problems in both a planar and geometric setting and to transfer the techniques used for recursive approximation schemes for geometric problems due to Adamaszek and Wiese (in Proceedings of the FOCS 2013, IEEE, 2013; in Proceedings of the SODA 2014, SIAM, 2014) and Har-Peled and Sariel (in Proceedings of the SOCG 2014, SIAM, 2014) to the setting of planar graphs. In particular, this yields a purely combinatorial viewpoint on these methods as a phenomenon in planar graphs.
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 a graph G in which the edges might have different lengths, 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 2 poly ( 1 / ϵ , log | D | )· nO ( 1 ), where n is the number of vertices of the input graph. We note that a QPTAS for Maximum Weight Independent Set of Objects would follow from existing work. However, our main contribution is to provide a unified framework that works for both problems in both a planar and geometric setting and to transfer the techniques used for recursive approximation schemes for geometric problems due to Adamaszek and Wiese (in Proceedings of the FOCS 2013, IEEE, 2013; in Proceedings of the SODA 2014, SIAM, 2014) and Har-Peled and Sariel (in Proceedings of the SOCG 2014, SIAM, 2014) to the setting of planar graphs. In particular, this yields a purely combinatorial viewpoint on these methods as a phenomenon in planar graphs.
KW - Approximation schemes
KW - Geometric set cover
KW - Independent set of objects
KW - Planar graphs
UR - http://www.scopus.com/inward/record.url?scp=85078049159&partnerID=8YFLogxK
U2 - 10.1007/s00453-019-00670-w
DO - 10.1007/s00453-019-00670-w
M3 - Article
AN - SCOPUS:85078049159
SN - 0178-4617
VL - 82
SP - 1703
EP - 1739
JO - Algorithmica
JF - Algorithmica
IS - 6
ER -