Volume 12 Number 2 (Apr. 2022)
Home > Archive > 2022 > Volume 12 Number 2 (Apr. 2022) >
IJAPM 2022 Vol.12(2): 10-21 ISSN: 2010-362X
DOI: 10.17706/ijapm.2022.12.2.10-21

A Primal-Dual Approximation Algorithm for the Minimum Soft Capacitated Power Cover Problem

Li Guan, Han Dai, Xiaofei Liu
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 ps of power (ps) may contain the same power) and the covering range of sensor s with any power pps 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 ks. The minimum soft capacitated power cover problem is to find a power set for each sensor denoted as {ps}sS such that each client point is assigned to one disk supported by {ps}sS satisfying that the number of client points assigned to d(s,p) is at most ks for any sS and pps. The objective is to minimize the value of {ps}sS, i.e. the total power ∑_(s:sS)∑_(p:pps)p. Our main result is to present a primal-dual f-approximation algorithm for the MSCPCP, where f=maxv∈V |{D∈D:v∈V(D)}| and Dis 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).

PREVIOUS PAPER
First page
NEXT PAPER
Last page

General Information

ISSN: 2010-362X (Online)
Abbreviated Title: Int. J. Appl. Phys. Math.
Frequency: Quarterly
DOI: 10.17706/IJAPM
Editor-in-Chief: Prof. Haydar Akca 
Abstracting/ Indexing:  Index Copernicus, IET INSPEC, CNKI, Chemical Abstracts Services (CAS), Nanowerk Database, Google Scholar, EBSCO, etc.
E-mail: ijapm@iap.org
  • Dec 27, 2021 News!

    IJAPM Vol 9 & Vol 10 have been indexed by Inspec   [Click]

  • Jun 16, 2022 News!

    IJAPM Vol 12, No 3 has been published with online version   [Click]

  • Mar 23, 2022 News!

    IJAPM Vol 12, No 2 has been published with online version   [Click]

  • Dec 27, 2021 News!

    IJAPM Vol 12, No 1 has been published with online version   [Click]

  • Sep 16, 2021 News!

    IJAPM Vol 11, No 4 has been published with online version   [Click]

  • Read more>>