Iterative partial rounding for vertex cover with hard capacities
From MaRDI portal
Publication:2223692
DOI10.1007/s00453-020-00749-9OpenAlexW3047485772MaRDI QIDQ2223692
Publication date: 1 February 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1606.08667
Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Capacitated domination problem
- Centrality of trees for capacitated \(k\)-center
- \(O(f)\) bi-criteria approximation for capacitated covering with hard capacities
- An analysis of the greedy algorithm for the submodular set covering problem
- Capacitated domination faster than \(O(2^n)\)
- A 1.488 approximation algorithm for the uncapacitated facility location problem
- Capacitated domination: problem complexity and approximation algorithms
- Solving Capacitated Dominating Set by using covering by subsets and maximum matching
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- An improved approximation algorithm for vertex cover with hard capacities
- Approximating $k$-Median via Pseudo-Approximation
- Set Cover Revisited: Hypergraph Cover with Hard Capacities
- A 5-Approximation for Capacitated Facility Location
- LP-Based Algorithms for Capacitated Facility Location
- Covering Problems with Hard Capacities
- Capacitated Domination and Covering: A Parameterized Perspective
- Dependent rounding and its applications to approximation algorithms
- A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover
- A Best Possible Heuristic for the k-Center Problem
- A linear-time approximation algorithm for the weighted vertex cover problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Greedy Strikes Back: Improved Facility Location Algorithms
- Capacitated vertex covering
- Approximation algorithms for partial covering problems
- An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
- On Uniform Capacitated k -Median Beyond the Natural LP Relaxation
- Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs
This page was built for publication: Iterative partial rounding for vertex cover with hard capacities