On Approximation of Max-Vertex-Cover

Han, Ye, Zhang, and Zhang

We consider the Max-Vertex-Cover (MVC) problem, i.e., find $k$ vertices from a undirected and edge-weighted graph $G=(V,E)$, where $|V|=n\ge k$, such that the total edge weight covered by the $k$ vertices is maximized. This problem was introduced by Petrank who proved that the existence of a $(1-\epi)$-approximation algorithm for MVC implies P=NP for some $\epi>0$. In this paper, we present a $3/4$-approximation algorithm for MVC, based on a linear programming (LP) relaxation. We also show that the guaranteed ratio can be improved by a simple greedy algorithm for $k > \frac{3}{4} n$, and a simple randomized algorithm for $k> \frac{1}{2} n$. Moreover, we study semidefinite programming (SDP) relaxation based approximation algorithms for MVC. We prove that, for a wide range of $k$, the SDP-based algorithms achieve the best performance guarantee among the four types of algorithms presented in this paper.

Working Paper, Department of Management Sciences, Henry B. Tippie College of Business, The University of Iowa, Iowa City, IA 52242, USA

Contact: yinyu-ye@uiowa.edu