TY - CHAP
T1 - Improved Approximation Algorithms for the Partial Vertex Cover Problem
T2 - Approximation Algorithms for Combinatorial OptimizationApproximation Algorithms for Combinatorial Optimization
Y1 - 2002
A1 - Halperin,Eran
A1 - Srinivasan, Aravind
ED - Jansen,Klaus
ED - Leonardi,Stefano
ED - Vazirani,Vijay
AB - 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.
JA - Approximation Algorithms for Combinatorial OptimizationApproximation Algorithms for Combinatorial Optimization
T3 - Lecture Notes in Computer Science
PB - Springer Berlin / Heidelberg
VL - 2462
SN - 978-3-540-44186-1
UR - http://dx.doi.org/10.1007/3-540-45753-4_15
ER -