1. PTAS FOR MINIMUM COST MULTICOVERING WITH DISKS.
- Author
-
ZIYUN HUANG, QILONG FENG, JIANXIN WANG, and JINHUI XU
- Subjects
- *
APPROXIMATION algorithms , *COMPUTATIONAL geometry , *DYNAMIC programming , *SENSOR networks , *POINT set theory - Abstract
In this paper, we study the following Minimum Cost Multicovering (MCMC) problem: Given a set of n client points C and a set of m server points S in a fixed dimensional Rd space, determine a set of disks centered at these server points so that each client point c is covered by at least k(c) disks and the total cost of these disks is minimized, where k(·) is a function that maps every client point to some nonnegative integer no more than m and the cost of each disk is measured by the \alpha th power of its radius for some constant α >0. MCMC is a fundamental optimization problem with applications in many areas such as wireless/sensor networking. Despite extensive research on this problem for about two decades, only constant approximations were known for general k. It has been a long standing open problem to determine whether a PTAS is possible. In this paper, we give an affirmative answer to this question by presenting the first PTAS for it. Our approach is based on a number of novel techniques, such as balanced recursive realization and bubble charging, and new counterintuitive insights to the problem. Particularly, we approximate each disk with a set of sub-boxes and optimize them at the subdisk level. This allows us to first compute an approximate disk cover through dynamic programming, and then obtain the desired disk cover through a balanced recursive realization procedure. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF