TY - GEN

T1 - PTAS for minimum cost multi-covering with disks

AU - Huang, Ziyun

AU - Feng, Qilong

AU - Wang, Jianxin

AU - Xu, Jinhui

N1 - Publisher Copyright:
Copyright © 2021 by SIAM

PY - 2021

Y1 - 2021

N2 - In this paper, we study the following Minimum Cost Multi-Covering (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 non-negative integer no more than m and the cost of each disk is measured by the α-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 in the past two decades, only constant approximations were known for general k. It has been an open problem for a long time 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 insights to the problem which are somewhat counter-intuitive. Particularly, we show that instead of optimizing each disk as a whole, it is possible to further approximate each disk with a set of sub-boxes and optimize them at the sub-disk level. This allows us to first compute an approximate disk cover with minimum cost through dynamic programming, and then obtain the desired disk cover through a balanced recursive realization procedure. Our techniques have the potential to be used to other geometric (covering) problems.

AB - In this paper, we study the following Minimum Cost Multi-Covering (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 non-negative integer no more than m and the cost of each disk is measured by the α-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 in the past two decades, only constant approximations were known for general k. It has been an open problem for a long time 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 insights to the problem which are somewhat counter-intuitive. Particularly, we show that instead of optimizing each disk as a whole, it is possible to further approximate each disk with a set of sub-boxes and optimize them at the sub-disk level. This allows us to first compute an approximate disk cover with minimum cost through dynamic programming, and then obtain the desired disk cover through a balanced recursive realization procedure. Our techniques have the potential to be used to other geometric (covering) problems.

UR - http://www.scopus.com/inward/record.url?scp=85105336579&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85105336579&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85105336579

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 840

EP - 859

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

A2 - Marx, Daniel

PB - Association for Computing Machinery

T2 - 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

Y2 - 10 January 2021 through 13 January 2021

ER -