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
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
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- A threshold of ln n for approximating set cover
- Approximation algorithms for NP-hard problems.
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Algorithms for facility location problems with outliers. (Extended abstract)
- Primal-Dual Schema for Capacitated Covering Problems
- Approximation algorithms for partial covering problems
- Title not available (Why is that?)
- A linear-time approximation algorithm for the weighted vertex cover problem
- Maximizing a monotone submodular function subject to a matroid constraint
- Improved performance of the greedy algorithm for partial cover
- Title not available (Why is that?)
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
- Approximating the k-multicut problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
- Approximation of Partial Capacitated Vertex Cover
Cited In (14)
- 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
- Title not available (Why is that?)
- 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
- On fair covering and hitting problems
- Approximation algorithm for prize-collecting vertex cover with fairness constraints
- Title not available (Why is that?)
- 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)
