Approximation algorithms for the partition vertex cover problem

DOI10.1016/J.TCS.2014.04.006zbMATH Open1379.68345OpenAlexW2148092222MaRDI QIDQ744047FDOQ744047

Authors Suman K. Bera, Shalmoli Gupta, Amit Kumar, Sambuddha Roy 

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

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

Recommendations

• Approximation algorithms for the partition vertex cover problem
• An iterative rounding 2-approximation algorithm for the \(k\)-partial vertex cover problem
• Approximation algorithms for partial covering problems
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 1947055

Cites Work

• scientific article; zbMATH DE number 5764796 (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 1445293 (Why is no real title available?)
• A linear-time approximation algorithm for the weighted vertex cover problem
• A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
• A threshold of ln n for approximating set cover
• Algorithms for facility location problems with outliers. (Extended abstract)
• Approximating the k-multicut problem
• Approximation algorithms for NP-hard problems.
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation algorithms for partial covering problems
• Approximation of Partial Capacitated Vertex Cover
• Improved performance of the greedy algorithm for partial cover
• Maximizing a monotone submodular function subject to a matroid constraint
• Primal-Dual Schema for Capacitated Covering Problems
• Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
• Submodular function maximization via the multilinear relaxation and contention resolution schemes

Cited In (15)

• A parameterized approximation scheme for generalized partial vertex cover
• Algorithms for covering multiple submodular constraints and applications
• Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
• Approximation algorithms for Min-k-overlap problems using the principal lattice of partitions approach
• The approximability of partial vertex covers in trees
• A constant approximation for colorful \(k\)-center
• On colorful vertex and edge cover problems
• Approximation algorithms for the partition vertex cover problem
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Approximation algorithm for vertex cover with multiple covering constraints
• Approximation algorithm for vertex cover with multiple covering constraints
• On fair covering and hitting problems
• Approximation algorithm for prize-collecting vertex cover with fairness constraints
• Tight approximation for partial vertex cover with hard capacities
• Approximation of Partial Capacitated Vertex Cover

This page was built for publication: Approximation algorithms for the partition vertex cover problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744047)