A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses

被引：0
作者：
Julián Mestre
机构：
[1] University of Maryland,Department of Computer Science
来源：
Algorithmica | 2009年 / 55卷
关键词：
Approximation algorithms; Vertex cover; Primal-dual algorithms;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We study the partial vertex cover problem. Given a graph G=(V,E), a weight function w:V→R+, and an integer s, our goal is to cover all but s edges, by picking a set of vertices with minimum weight. The problem is clearly NP-hard as it generalizes the well-known vertex cover problem. We provide a primal-dual 2-approximation algorithm which runs in O(nlog n+m) time. This represents an improvement in running time from the previously known fastest algorithm.
引用
收藏
页码：227 / 239
页数：12
相关论文
共 21 条
[1]  
Bar-Yehuda R.(2001)Using homogeneous weights for approximating the partial cover problem J. Algorithms 39 137-144
[2]  
Bar-Yehuda R.(1981)A linear time approximation algorithm for approximating the weighted vertex cover J. Algorithms 2 198-203
[3]  
Even S.(1985)A local-ratio theorem for approximating the weighted vertex cover problem Ann. Discret. Math. 25 27-46
[4]  
Bar-Yehuda R.(1983)A modification of the greedy algorithm for vertex cover Inf. Process. Lett. 16 23-25
[5]  
Even S.(2004)Approximation algorithms for partial covering problems J. Algorithms 53 55-84
[6]  
Clarkson K.L.(2006)Dependent rounding and its applications to approximation algorithms J. ACM 53 324-360
[7]  
Gandhi R.(2003)Capacitated vertex covering J. Algorithms 48 257-270
[8]  
Khuller S.(2002)Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs SIAM J. Comput. 31 1608-1623
[9]  
Srinivasan A.(1982)Approximation algorithms for the set covering and vertex cover problems SIAM J. Comput. 11 555-556
[10]  
Gandhi R.(2001)Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation J. ACM 48 274-296
123