Hybrid approximation for minimum-cost target coverage in wireless sensor networks

摘要

This paper presents a hybrid approximation scheme for the Max-SNPcomplete minimum-cost target coverage problem in wireless sensor networks. LP-rounding and set-cover selection are polynomial-time approximations for this problem. Our hybrid scheme combines these two methods using a crafted convex combination. We show that the hybrid scheme with appropriately chosen coefficients produces much better approximations than either of the two methods used alone. We show that, through a large number of numerical experiments, the hybrid scheme never exceeds an approximation ratio of 1.14, providing up to 14.86% improvement over the best approximations previously known.