Resumen
In this paper, we consider the minimum power cover problem with submodular penalty (SPMPC). Given a set U of n users, a set S of m sensors and a penalty function ??:2???R+
p
:
2
U
?
R
+
on the plane, the relationship that adjusts the power ??(??)
p
(
s
)
of each sensor s and its corresponding radius ??(??)
r
(
s
)
is: ??(??)=??·??(??)??
p
(
s
)
=
c
·
r
(
s
)
a
, where ??>0
c
>
0
and ??=1
a
=
1
. The SPMPC problem is to determine the power assignment on each sensor such that each user ?????
u
?
U
is either covered by the sensor or penalized and the sum of the total power consumed by sensors in S plus the penalty of all uncovered users is minimized, the penalty here is determined by the submodular function. Based on the primal dual technique, we design an ??(??)
O
(
a
)
-approximation algorithm.