# Improved Approximation Algorithms for the Partial Vertex Cover Problem

 Title Improved Approximation Algorithms for the Partial Vertex Cover Problem Publication Type Book Chapters Year of Publication 2002 Authors Halperin E, Srinivasan A Editor Jansen K, Leonardi S, Vazirani V Book Title Approximation Algorithms for Combinatorial OptimizationApproximation Algorithms for Combinatorial Optimization Series Title Lecture Notes in Computer Science Volume 2462 Pagination 161 - 174 Publisher Springer Berlin / Heidelberg ISBN Number 978-3-540-44186-1 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 $$łeft( 2 - \Theta łeft( \tfracłn łn d ł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. URL http://dx.doi.org/10.1007/3-540-45753-4_15