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

Autor: Pilipczuk, Michal, Leeuwen, Erik Jan van, Wiese, Andreas, Azar, Yossi, Bast, Hannah, Herman, Grzegorz, Sub Algorithms and Complexity, Algorithms and Complexity
Přispěvatelé: Sub Algorithms and Complexity, Algorithms and Complexity
Jazyk: angličtina
Rok vydání: 2020
Předmět:
FOS: Computer and information sciences
General Computer Science
Minimum weight
0102 computer and information sciences
02 engineering and technology
Disjoint sets
Quasi-polynomial
01 natural sciences
Combinatorics
Geometric set cover
symbols.namesake
Computer Science - Data Structures and Algorithms
0202 electrical engineering
electronic engineering
information engineering
QPTAS
Data Structures and Algorithms (cs.DS)
Voronoi diagram
Mathematics
Approximation schemes
000 Computer science
knowledge
general works
Applied Mathematics
Multiplicative function
Covering problems
Planar graphs
planar graphs
Computer Science Applications
Vertex (geometry)
Planar graph
010201 computation theory & mathematics
68W25 (Approximation algorithms)
Independent set of objects
Independent set
Computer Science
symbols
020201 artificial intelligence & image processing
Zdroj: 26th Annual European Symposium on Algorithms, 112. Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH
Algorithmica, 82(6), 1703. Springer New York
ISSN: 0178-4617
Popis: We consider two optimization problems in planar graphs. In Maximum Weight Independent Set of Objects we are given a graph $G$ and a family $\mathcal{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 $\mathcal{D}$ consisting of pairwise disjoint objects. In Minimum Weight Distance Set Cover we are given an edge-weighted graph $G$, two sets $\mathcal{D},\mathcal{C}$ of vertices of $G$, where vertices of $\mathcal{D}$ have prescribed weights, and a nonnegative radius $r$. The task is to find a minimum-weight subset of $\mathcal{D}$ such that every vertex of $\mathcal{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^{\mathrm{poly}(1/\epsilon,\log |\mathcal{D}|)}\cdot n^{\mathcal{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 to the setting of planar graphs. In particular, this yields a purely combinatorial viewpoint on these methods.
Comment: 31 pages, 5 figures, accepted at ESA 2018
Databáze: OpenAIRE
Externí odkaz: