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

DOI10.1007/s10255-014-0282-2zbMath1295.05241OpenAlexW1981418852MaRDI QIDQ403490

Jian-hua Tu, Feng-mei Yang, Jun-feng Du

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Related Items (1)

Lift \& project systems performing on the partial-vertex-cover polytope

Cites Work

• A new polynomial-time algorithm for linear programming
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Combinatorial algorithms on a class of graphs
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Iterative Methods in Combinatorial Optimization
• Approximation algorithms for partial covering problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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