Iterative partial rounding for vertex cover with hard capacities

DOI10.1007/s00453-020-00749-9OpenAlexW3047485772MaRDI QIDQ2223692

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

zbMATH Keywords

approximation algorithmvertex coveriterative roundinghard capacity

Mathematics Subject Classification ID

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