@inbook {17604,
title = {Improved Approximation Algorithms for the Partial Vertex Cover Problem},
booktitle = {Approximation Algorithms for Combinatorial OptimizationApproximation Algorithms for Combinatorial Optimization},
series = {Lecture Notes in Computer Science},
volume = {2462},
year = {2002},
month = {2002///},
pages = {161 - 174},
publisher = {Springer Berlin / Heidelberg},
organization = {Springer Berlin / Heidelberg},
abstract = {The partial vertex cover problem is a generalization of the vertex cover problem:given an undirected graph G = ( V,E ) and an integer k , we wish to choose a minimum number of vertices such that at least k edges are covered. Just as for vertex cover, 2-approximation algorithms are known for this problem, and it is of interest to see if we can do better than this.The current-best approximation ratio for partial vertex cover, when parameterized by the maximum degree d of G , is (2 - Θ (1/ d )).We improve on this by presenting a $$ {\l}eft( 2 - \Theta {\l}eft( \tfrac{\l}n {\l}n d {\l}n d \right) \right) $$ -approximation algorithm for partial vertex cover using semidefinite programming, matching the current-best bound for vertex cover. Our algorithmuses a new rounding technique, which involves a delicate probabilistic analysis.},
isbn = {978-3-540-44186-1},
url = {http://dx.doi.org/10.1007/3-540-45753-4_15},
author = {Halperin,Eran and Srinivasan, Aravind},
editor = {Jansen,Klaus and Leonardi,Stefano and Vazirani,Vijay}
}