We consider the max-vertex-cover (MVC) problem, i.e., find k vertices from an undirected and edge-weighted graph G=(V,E), where |V|=n≥k, such that the total edge weight covered by the k vertices is maximized. There is a 3/4-approximation algorithm for MVC, based on a linear programming relaxation. We show that the guaranteed ratio can be improved by a simple greedy algorithm for k>(3/4)n, and a simple randomized algorithm for k>(1/2)n. Furthermore, we study a semidefinite programming (SDP) relaxation based approximation algorithm for MVC. We show that, for a range of k, our SDP-based algorithm achieves the best performance guarantee among the four types of algorithms mentioned in this paper.
