Iterative partial rounding for vertex cover with hard capacities

DOI10.1007/S00453-020-00749-9OpenAlexW3047485772MaRDI QIDQ2223692FDOQ2223692

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

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)