Approximate Algorithms for Vertex Cover Problems in WSN Topology Design
Yuanchao Liu, Jianxi Fan, Dajin Wang, Hongwei Du, Shukui Zhang and Jing Lv
The Vertex Cover (VC) problem is a classical optimization problem that can be applied in topology design in Wireless Sensor Networks (WSNs). In this paper, we first propose two polynomial time approximation schemes (PTASs) for the Minimum Vertex Cover (MVC) problem and the Minimum Weighted Vertex Cover (MWVC) problem in growth-bounded graphs. We then propose an approximation algorithm, with a performance guarantee of (1 + 2ε/(1 – ε)) for sufficiently small ε>0, for the Minimum Connected Vertex Cover (MCVC) problem. In contrast to previously proposed schemes for VC problems, our approach does not assume geometric representation of vertices in growth-bounded graphs. We also prove that the running times of the proposed algorithms are bounded by a polynomial in terms of the graph size and the input ε. We evaluate the performance of our algorithms through simulation.
Keywords: Wireless sensor networks, vertex cover, approximation algorithm, bounded degree.