Approximation algorithms for the partition vertex cover problem

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

zbMATH Keywords

approximation algorithmvertex coverLP roundingknapsack cover inequality

Mathematics Subject Classification ID

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