Hybrid approximation for minimum-cost target coverage in wireless sensor networks |
| |
Authors: | Zheng Fang Jie Wang |
| |
Institution: | 1.Department of Computer Science,University of Massachusetts,Lowell,USA |
| |
Abstract: | This paper presents a hybrid approximation scheme for the Max-SNP-complete 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|