Iterative partial rounding for vertex cover with hard capacities
From MaRDI portal
Publication:2223692
DOI10.1007/S00453-020-00749-9OpenAlexW3047485772MaRDI QIDQ2223692FDOQ2223692
Authors: Mong-Jen Kao 
Publication date: 1 February 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1606.08667
Recommendations
- Iterative partial rounding for vertex cover with hard capacities
- Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs
- Tight approximation for partial vertex cover with hard capacities
- Tight approximation for partial vertex cover with hard capacities
- Improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs
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
Cited In (3)
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)
