Approximation algorithms for the minimum power cover problem with submodular/linear penalties
In this paper, we introduce the minimum power cover problem with submodular and linear
penalties. Suppose U is a set of users and S is a set of sensors in a d-dimensional space R
d with d≥ 2. Each sensor can adjust its power and the relationship between the power p (s)
and the radius r (s) of the service area of sensor s satisfies p (s)= c⋅ r (s) α, where c> 0 and
α≥ 1. Let p be the power assignment for each sensor and R be the set of users who are not
covered by any sensor supported by p. The objective is to minimize the total power of p plus …
penalties. Suppose U is a set of users and S is a set of sensors in a d-dimensional space R
d with d≥ 2. Each sensor can adjust its power and the relationship between the power p (s)
and the radius r (s) of the service area of sensor s satisfies p (s)= c⋅ r (s) α, where c> 0 and
α≥ 1. Let p be the power assignment for each sensor and R be the set of users who are not
covered by any sensor supported by p. The objective is to minimize the total power of p plus …
In this paper, we introduce the minimum power cover problem with submodular and linear penalties. Suppose U is a set of users and S is a set of sensors in a d-dimensional space R d with d≥ 2. Each sensor can adjust its power and the relationship between the power p (s) and the radius r (s) of the service area of sensor s satisfies p (s)= c⋅ r (s) α, where c> 0 and α≥ 1. Let p be the power assignment for each sensor and R be the set of users who are not covered by any sensor supported by p. The objective is to minimize the total power of p plus the rejected penalty of R. For a submodular penalty function that is normalized and nondecreasing, we present a combinatorial primal-dual (3 α+ 1)-approximation algorithm. For the case in which the submodular penalty function is linear, we present a polynomial time approximation scheme based on a plane subdivision technique.
Elsevier
