A primal-dual approximation algorithm for partial vertex cover: Making educated guesses

DOI10.1007/s00453-007-9003-zzbMath1194.68262MaRDI QIDQ2391176

Julián Mestre

Publication date: 24 July 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9003-z

zbMATH Keywords

approximation algorithms; vertex cover; primal-dual algorithms

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68W25: Approximation algorithms

Related Items

Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs, Tight approximation for partial vertex cover with hard capacities, On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs, Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems, On Partial Covering For Geometric Set Systems, Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs, On the partial vertex cover problem in bipartite graphs -- a parameterized perspective, Approximation algorithms for the partition vertex cover problem, Lift \& project systems performing on the partial-vertex-cover polytope, Approximation algorithm for vertex cover with multiple covering constraints, Capacitated Arc Stabbing, Tight approximation for partial vertex cover with hard capacities, The Approximability of Partial Vertex Covers in Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using Homogeneous Weights for Approximating the Partial Cover Problem
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Dependent rounding and its applications to approximation algorithms
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Capacitated vertex covering
• Approximation algorithms for partial covering problems
• Automata, Languages and Programming