Abstract—In this paper, we study the minimum soft capacitated power cover problem: Given a set V of n client points, a set S of m server points on a plane. Each sensor s can be arranged by set p_s of power (p_s) may contain the same power) and the covering range of sensor s with any power p∈p_s is a disk d(s,p) of radius r(s) satisfying p=cr(s)^α. Where c>0 and α≥1are two constants. Any disk center at sensor s has a capacity k_s. The minimum soft capacitated power cover problem is to find a power set for each sensor denoted as {p_s}_s∈S such that each client point is assigned to one disk supported by {p_s}_s∈S satisfying that the number of client points assigned to d(s,p) is at most k_s for any s∈S and p∈p_s. The objective is to minimize the value of {p_s}_s∈S, i.e. the total power ∑_(s:s∈S)∑_(p:p∈p_s)p. Our main result is to present a primal-dual f-approximation algorithm for the MSCPCP, where f=max_v∈V |{D∈D:v∈V(D)}| and D_is a disk set related to V and S.

Index Terms—Approximation algorithm, primal-dual, soft capacitated power cover.

Li Guan, Han Dai is with School of Mathematics and Statistics, Yunnan University, Kunming, China. Xiaofei Liu is with School of Information Science and Engineering, Yunnan University, Kunming, China.

Cite:Li Guan, Han Dai, Xiaofei Liu, "A Primal-Dual Approximation Algorithm for the Minimum Soft Capacitated Power Cover Problem," International Journal of Applied Physics and Mathematics vol. 12, no. 2, pp. 10-21, 2022.
 

Copyright © 2022 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).