Name
Abstract | ||
|---|---|---|
In this paper, we design the first polynomial time approximation schemes for the Set Cover and Dominating Set problems when the underlying sets are non-piercing regions (which include pseudodisks). Earlier, PTASs were known only in the setting where the regions were disks. These techniques relied heavily on the circularity of the disks. We develop new techniques to show that a simple local search algorithm yields a PTAS for the problems on non-piercing regions. We then consider the Capacitated Region Packing problem. Here, the input consists of a set of points with capacities, and a set of regions. The objective is to pick a maximum cardinality subset of regions so that no point is covered by more regions than its capacity. We show that this problem admits a PTAS when the regions are -admissible regions (pseudodisks are 2-admissible), and the capacities are bounded by some constant. Our result settles a conjecture of Har-Peled from 2014 in the affirmative. The conjecture was for a weaker version of the problem, namely when the regions are pseudodisks, the capacities are uniform, and the point set consists of all points in the plane. Finally, we consider the Capacitated Point Packing problem. In this setting, the regions have capacities, and our objective is to find a maximum cardinality subset of points such that no region has more points than its capacity. We show that this problem admits a PTAS when the capacity is unity. This extends a result of Ene et al. from 2012. |
Year | DOI | Venue |
|---|---|---|
2018 | https://doi.org/10.1007/s00454-018-9983-2 | Discrete & Computational Geometry |
Keywords | Field | DocType |
Local search,Set cover,Dominating set,Capacitated packing,Approximation algorithms,52C15,05C65,05C69,68Q25,68W25,68W05 | Approximation algorithm,Set cover problem,Dominating set,Combinatorics,Packing problems,Cardinality,Time complexity,Conjecture,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
60 | 2 | 0179-5376 |
Citations | PageRank | References |
0 | 0.34 | 18 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aniket Basu Roy | 1 | 3 | 2.78 |
| Sathish Govindarajan | 2 | 110 | 12.84 |
| Rajiv Raman | 3 | 185 | 16.47 |
| Saurabh Ray | 4 | 228 | 24.28 |