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