Approximation algorithms for the partition vertex cover problem
From MaRDI portal
Publication:744047
DOI10.1016/j.tcs.2014.04.006zbMath1379.68345OpenAlexW2148092222MaRDI QIDQ744047
Suman K. Bera, Amit Kumar, Sambuddha Roy, Shalmoli Gupta
Publication date: 6 October 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2014.04.006
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (8)
Algorithms for covering multiple submodular constraints and applications ⋮ On fair covering and hitting problems ⋮ Tight approximation for partial vertex cover with hard capacities ⋮ On colorful vertex and edge cover problems ⋮ A parameterized approximation scheme for generalized partial vertex cover ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximation algorithm for vertex cover with multiple covering constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved performance of the greedy algorithm for partial cover
- A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
- A threshold of ln n for approximating set cover
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- Primal-Dual Schema for Capacitated Covering Problems
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Saving an epsilon
- Approximating the k-multicut problem
- A linear-time approximation algorithm for the weighted vertex cover problem
- Approximation algorithms for partial covering problems
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Approximation of Partial Capacitated Vertex Cover
This page was built for publication: Approximation algorithms for the partition vertex cover problem