2026-07-23T04:54:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11247 2024-03-06T10:47:47Z ddc:004 open_access

Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint Huang, Chien-Chung Mari, Mathieu Mathieu, Claire Mitchell, Joseph S. B. Mustafa, Nabil H. approximation algorithm submodular function optimisation unit disk graph connectivity constraint 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chien-Chung Huang and Mathieu Mari and Claire Mathieu and Joseph S. B. Mitchell and Nabil H. Mustafa 2019 Is Part Of LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2019.32 urn:nbn:de:0030-drops-112471 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.32 eng https://creativecommons.org/licenses/by/3.0/legalcode