doi: 10.17706/ijapm.2022.12.2.10-21
A Primal-Dual Approximation Algorithm for the Minimum Soft Capacitated Power Cover Problem
- 1 School of Mathematics and Statistics, Yunnan University, Kunming, China
- 2 School of Information Science and Engineering, Yunnan University, Kunming, China.
Abstract
In this paper, we study the minimum soft capacitated power cover problem: Given a set <em>V </em>of <em>n</em> client points, a set <em>S</em> of <em>m</em> server points on a plane. Each sensor <em>s</em> can be arranged by set <em>p<sub>s</sub></em> of power (<em>p<sub>s</sub></em>) may contain the same power) and the covering range of sensor s with any power <em>p</em>∈<em>p<sub>s</sub></em> is a disk <em>d(s,p)</em> of radius <em>r(s)</em> satisfying <em>p=cr(s)<sup>α</sup></em>. Where <em>c</em>>0 and <em>α</em>≥1are two constants. Any disk center at sensor s has a capacity <em>k<sub>s</sub></em>. The minimum soft capacitated power cover problem is to find a power set for each sensor denoted as {<em>p<sub>s</sub></em>}<sub><em>s</em>∈<em>S</em></sub> such that each client point is assigned to one disk supported by {<em>p<sub>s</sub></em>}<sub><em style="font-size: 10px;">s</em><span style="font-size: 10px;">∈</span><em style="font-size: 10px;">S</em></sub> satisfying that the number of client points assigned to <em>d(s,p)</em> is at most <em>k<sub>s</sub></em> for any <em style="font-size: 10px;">s</em><span style="font-size: 10px;">∈</span><em style="font-size: 10px;">S</em> and <em>p</em>∈<em>p<sub>s</sub></em>. The objective is to minimize the value of {<em>p<sub>s</sub></em>}<sub><em style="font-size: 10px;">s</em><span style="font-size: 10px;">∈</span><em style="font-size: 10px;">S</em></sub>, i.e. the total power ∑_(<em>s</em>:<em style="font-size: 10px;">s</em><span style="font-size: 10px;">∈</span><em style="font-size: 10px;">S</em>)∑_(<em>p:p</em>∈<em>p<sub>s</sub></em>)<em>p</em>. Our main result is to present a primal-dual <em>f-</em>approximation algorithm for the MSCPCP, where<em> f</em>=max<sub><em>v∈V </em></sub>|{<em>D∈D:v∈V(D)</em>}| and <em>D<sub>is</sub></em> a disk set related to <em>V</em> and <em>S.</em>
Keywords
- Approximation algorithm
- primal-dual
- soft capacitated power cover
How to Cite
Li Guan, Han Dai, and 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. https://doi.org/ 10.17706/ijapm.2022.12.2.10-21
Copyright & License
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).