An iterative rounding 2-approximation algorithm for the k-partial vertex cover problem

DOI10.1007/S10255-014-0282-2zbMATH Open1295.05241OpenAlexW1981418852MaRDI QIDQ403490FDOQ403490

Authors: Jianhua Tu, Junfeng Du, Fengmei Yang 

Publication date: 29 August 2014

Published in: Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10255-014-0282-2

Recommendations

• scientific article; zbMATH DE number 1947055
• Approximation algorithms for partial covering problems
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 1754596
• A primal-dual approximation algorithm for partial vertex cover: Making educated guesses

zbMATH Keywords

combinatorial optimizationapproximation algorithmiterative rounding\(k\)-partial vertex cover

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• A new polynomial-time algorithm for linear programming
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Title not available (Why is that?)
• Graph theory with applications
• Title not available (Why is that?)
• Approximation algorithms for partial covering problems
• Title not available (Why is that?)
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Iterative methods in combinatorial optimization.
• Combinatorial algorithms on a class of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (9)

• Lift \& project systems performing on the partial-vertex-cover polytope
• A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
• Computing small partial coverings
• Approximation algorithms for the partition vertex cover problem
• Approximation algorithms for the partition vertex cover problem
• Title not available (Why is that?)
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Some results on incremental vertex cover problem
• Approximation algorithms for partial covering problems

This page was built for publication: An iterative rounding 2-approximation algorithm for the \(k\)-partial vertex cover problem

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