TY - GEN
T1 - Maximizing covered area in the Euclidean plane with connectivity constraint
AU - Huang, Chien Chung
AU - Mari, Mathieu
AU - Mathieu, Claire
AU - Mitchell, Joseph S.B.
AU - Mustafa, Nabil H.
N1 - Publisher Copyright:
© Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Joseph S. B. Mitchell, and Nabil H. Mustafa.
PY - 2019/9
Y1 - 2019/9
N2 - Given a set D of n unit disks in the plane and an integer k ≤ n, the maximum area connected subset problem asks for a set D' ⊆ D of size k that maximizes the area of the union of disks, under the constraint that this union is connected. This problem is motivated by wireless router deployment and is a special case of maximizing a submodular function under a connectivity constraint. We prove that the problem is NP-hard and analyze a greedy algorithm, proving that it is a ½- approximation. We then give a polynomial-time approximation scheme (PTAS) for this problem with resource augmentation, i.e., allowing an additional set of εk disks that are not drawn from the input. Additionally, for two special cases of the problem we design a PTAS without resource augmentation.
AB - Given a set D of n unit disks in the plane and an integer k ≤ n, the maximum area connected subset problem asks for a set D' ⊆ D of size k that maximizes the area of the union of disks, under the constraint that this union is connected. This problem is motivated by wireless router deployment and is a special case of maximizing a submodular function under a connectivity constraint. We prove that the problem is NP-hard and analyze a greedy algorithm, proving that it is a ½- approximation. We then give a polynomial-time approximation scheme (PTAS) for this problem with resource augmentation, i.e., allowing an additional set of εk disks that are not drawn from the input. Additionally, for two special cases of the problem we design a PTAS without resource augmentation.
KW - Approximation algorithm
KW - Connectivity constraint
KW - Submodular function optimisation
KW - Unit disk graph
UR - https://www.scopus.com/pages/publications/85072869812
U2 - 10.4230/LIPIcs.APPROX-RANDOM.2019.32
DO - 10.4230/LIPIcs.APPROX-RANDOM.2019.32
M3 - Conference contribution
AN - SCOPUS:85072869812
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019
A2 - Achlioptas, Dimitris
A2 - Vegh, Laszlo A.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 23rd International Conference on Randomization and Computation, APPROX/RANDOM 2019
Y2 - 20 September 2019 through 22 September 2019
ER -