##
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