Abstract
In this article dedicated to Professor Yue Minyi on the occasion of his 95th birthday, we present a new polynomial-time approximation scheme for the well-known Maximum Lifetime Coverage problem in wireless sensor networks. For any , this scheme contains an approximation algorithm with performance
, which improves the performance ratio
of previously known approximation in the literature.
Acknowledgments
All authors are Professor Minyi Yue’s student or student’s students. They respect and appreciate very much the great contributions of Professor Yue on research and education.
Notes
1 By ‘maximal position on the left side’ we mean the disk has the leftmost intersection point with some horizontal line, and that intersection point is at least distance left of the cell
among all sensing disks of sensors lying in
. For example, in Figure ,
and
have maximal position on the right side, due to their intersections with lines
and
, respectively, but
does not have maximal position on the right side. Similar meaning holds for ‘maximal position on the right side’, ‘maximal position on the upper side’ and ‘maximal position on the lower side’.
This work was supported in part by the National Science Foundation of USA under [grant number CNS101630], [grant number CCF0829993].