Improved bounds for metric capacitated covering problems
From MaRDI portal
Publication:6107884
DOI10.1007/s00453-022-01084-xOpenAlexW3035986120MaRDI QIDQ6107884
Publication date: 28 June 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12875/
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A 3-approximation algorithm for the facility location problem with uniform capacities
- Improved results on geometric hitting set problems
- Centrality of trees for capacitated \(k\)-center
- Improved approximation algorithms for capacitated facility location problems
- An analysis of the greedy algorithm for the submodular set covering problem
- A constant-factor approximation algorithm for the \(k\)-median problem
- Almost optimal set covers in finite VC-dimension
- A PTAS for the cardinality constrained covering with unit balls
- An improved approximation algorithm for vertex cover with hard capacities
- Improved Approximation Guarantees for Lower-Bounded Facility Location
- A 5-Approximation for Capacitated Facility Location
- WEIGHTED GEOMETRIC SET COVER PROBLEMS REVISITED
- LP-Based Algorithms for Capacitated Facility Location
- A threshold of ln n for approximating set cover
- An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation
- Covering Problems with Hard Capacities
- Data Collection for the Sloan Digital Sky Survey—A Network-Flow Heuristic
- How to Allocate Network Centers
- The Capacitated K-Center Problem
- Analysis of a Local Search Heuristic for Facility Location Problems
- Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs
- Iterative Partial Rounding for Vertex Cover with Hard Capacities
- On Uniform Capacitated k -Median Beyond the Natural LP Relaxation
- On Uniform Capacitated k-Median Beyond the Natural LP Relaxation
- Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems
- Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts
This page was built for publication: Improved bounds for metric capacitated covering problems
