Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks

Yingli Ran, Xiaohui Huang, Zhao Zhang () and Ding-Zhu Du ()
Additional contact information
Yingli Ran: Zhejiang Normal University
Xiaohui Huang: Zhejiang Normal University
Zhao Zhang: Zhejiang Normal University
Ding-Zhu Du: University of Texas at Dallas

Journal of Global Optimization, 2021, vol. 80, issue 3, No 7, 677 pages

Abstract: Abstract In this paper, we consider the wireless sensor network in which the power of each sensor is adjustable. Given a set of sensors and a set of targets, we study a problem of minimizing the total power such that the coverage of targets meets partial multi-cover requirement, that is, there are at least a given number of targets each covered by a given number of sensors (this number is called the covering requirement for the target). This is called the minimum power partial multi-cover problem (MinPowerPMC) in a wireless sensor network. Under the assumption that the covering requirements for all targets are upper bounded by a constant, we design the first PTAS for the MinPowerPMC problem, that is, for any $$\varepsilon >0$$ ε > 0 , a polynomial-time $$(1+\varepsilon )$$ ( 1 + ε ) -approximation.

Keywords: Minimum power partial multi cover; Wireless sensor networks; Approximation algorithm; PTAS (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-021-01033-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:80:y:2021:i:3:d:10.1007_s10898-021-01033-y

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-021-01033-y

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().