摘要：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.
关键词：approximation algorithm; submodular function optimisation; unit disk graph; connectivity constraint
