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

DOI10.1007/S00453-007-9003-ZzbMATH Open1194.68262OpenAlexW2178856181MaRDI QIDQ2391176FDOQ2391176

Authors 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 algorithmsvertex coverprimal-dual algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximation algorithms for partial covering problems
• scientific article; zbMATH DE number 1754596
• An iterative rounding 2-approximation algorithm for the \(k\)-partial vertex cover problem
• Improved Upper Bounds for Partial Vertex Cover

Cites work

• scientific article; zbMATH DE number 3869066 (Why is no real title available?)
• scientific article; zbMATH DE number 1182766 (Why is no real title available?)
• scientific article; zbMATH DE number 1947055 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• A linear-time approximation algorithm for the weighted vertex cover problem
• Algorithms for facility location problems with outliers. (Extended abstract)
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation algorithms for NP-hard problems.
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation algorithms for partial covering problems
• Automata, Languages and Programming
• Capacitated vertex covering
• Dependent rounding and its applications to approximation algorithms
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• Using homogeneous weights for approximating the partial cover problem

Cited in

(19)

• Capacitated Arc Stabbing
• Analyzing the optimal neighborhood: algorithms for partial and budgeted connected dominating set problems
• On the partial vertex cover problem in bipartite graphs -- a parameterized perspective
• Approximation algorithms for partial vertex covers in trees
• On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
• Partial vertex cover and budgeted maximum coverage in bipartite graphs
• Lift \& project systems performing on the partial-vertex-cover polytope
• Approximation algorithm for vertex cover with multiple covering constraints
• Using homogeneous weights for approximating the partial cover problem
• Tight approximation for partial vertex cover with hard capacities
• An iterative rounding 2-approximation algorithm for the \(k\)-partial vertex cover problem
• Approximation algorithms for the partition vertex cover problem
• Improved Upper Bounds for Partial Vertex Cover
• Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
• The approximability of partial vertex covers in trees
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• On partial covering for geometric set systems
• Tight approximation for partial vertex cover with hard capacities

This page was built for publication: A primal-dual approximation algorithm for partial vertex cover: Making educated guesses

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2391176)