An iterative rounding 2-approximation algorithm for the \(k\)-partial vertex cover problem
From MaRDI portal
Publication:403490
DOI10.1007/s10255-014-0282-2zbMath1295.05241MaRDI 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
90C27: Combinatorial optimization
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
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