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

DOI10.1007/S10255-014-0282-2MaRDI QIDQ403490zbMATHOpenAlexFDO

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

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)

Recommendations

• Publication:4411285
• Approximation algorithms for partial covering problems
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Publication:4535021
• A primal-dual approximation algorithm for partial vertex cover: Making educated guesses

Cites work

• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 1305393 (Why is no real title available?)
• scientific article; zbMATH DE number 1182766 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• scientific article; zbMATH DE number 1416629 (Why is no real title available?)
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A new polynomial-time algorithm for linear programming
• Approximation algorithms for partial covering problems
• Combinatorial algorithms on a class of graphs
• Graph theory with applications
• Iterative methods in combinatorial optimization.
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(9)

• scientific article; zbMATH DE number 1947055 (Why is no real title available?)
• A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
• Lift \& project systems performing on the partial-vertex-cover polytope
• Approximation algorithms for partial covering problems
• Approximation algorithms for the partition vertex cover problem
• Some results on incremental vertex cover problem
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximation algorithms for the partition vertex cover problem
• Computing small partial coverings

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)