Improved Approximation Algorithms for the Partial Vertex Cover Problem

TitleImproved Approximation Algorithms for the Partial Vertex Cover Problem
Publication TypeBook Chapters
Year of Publication2002
AuthorsHalperin E, Srinivasan A
EditorJansen K, Leonardi S, Vazirani V
Book TitleApproximation Algorithms for Combinatorial OptimizationApproximation Algorithms for Combinatorial Optimization
Series TitleLecture Notes in Computer Science
Pagination161 - 174
PublisherSpringer Berlin / Heidelberg
ISBN Number978-3-540-44186-1

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.