Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.32
URN: urn:nbn:de:0030-drops-112471
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11247/
Huang, Chien-Chung ; Mari, Mathieu ; Mathieu, Claire ; Mitchell, Joseph S. B. ; Mustafa, Nabil H.
Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint
| pdf-format: |
|
Abstract
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' subseteq 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 1/2-approximation. We then give a polynomial-time approximation scheme (PTAS) for this problem with resource augmentation, i.e., allowing an additional set of epsilon k disks that are not drawn from the input. Additionally, for two special cases of the problem we design a PTAS without resource augmentation.
BibTeX - Entry
@InProceedings{huang_et_al:LIPIcs:2019:11247,
author = {Chien-Chung Huang and Mathieu Mari and Claire Mathieu and Joseph S. B. Mitchell and Nabil H. Mustafa},
title = {{Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {32:1--32:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11247},
URN = {urn:nbn:de:0030-drops-112471},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.32},
annote = {Keywords: approximation algorithm, submodular function optimisation, unit disk graph, connectivity constraint}
}
| Keywords: | approximation algorithm, submodular function optimisation, unit disk graph, connectivity constraint | |
| Seminar: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 17.09.2019 |
