Advertisement
Published in:
07-04-2020
A primal-dual algorithm for the minimum power partial cover problem
Published in: Journal of Combinatorial Optimization | Issue 3/2022
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
In this paper, we study the minimum power partial cover problem (MinPPC). Suppose X is a set of points and \({\mathcal {S}}\) is a set of sensors on the plane, each sensor can adjust its power and the covering range of a sensor s with power p(s) is a disk of radius r(s) satisfying \(p(s)=c\cdot r(s)^\alpha \). Given an integer \(k\le |X|\), the MinPPC problem is to determine the power assignment on every sensor such that at least k points are covered and the total power consumption is the minimum. We present a primal-dual algorithm for MinPPC with approximation ratio at most \(3^{\alpha }\). This ratio coincides with the best known ratio for the minimum power full cover problem, and improves previous ratio \((12+\varepsilon )\) for MinPPC which was obtained only for \(\alpha =2\).