Centrality of trees for capacitated k-center
From MaRDI portal
Publication:896276
Abstract: There is a large discrepancy in our understanding of uncapacitated and capacitated versions of network location problems. This is perhaps best illustrated by the classical k-center problem: there is a simple tight 2-approximation algorithm for the uncapacitated version whereas the first constant factor approximation algorithm for the general version with capacities was only recently obtained by using an intricate rounding algorithm that achieves an approximation guarantee in the hundreds. Our paper aims to bridge this discrepancy. For the capacitated k-center problem, we give a simple algorithm with a clean analysis that allows us to prove an approximation guarantee of 9. It uses the standard LP relaxation and comes close to settling the integrality gap (after necessary preprocessing), which is narrowed down to either 7, 8 or 9. The algorithm proceeds by first reducing to special tree instances, and then solves such instances optimally. Our concept of tree instances is quite versatile, and applies to natural variants of the capacitated k-center problem for which we also obtain improved algorithms. Finally, we give evidence to show that more powerful preprocessing could lead to better algorithms, by giving an approximation algorithm that beats the integrality gap for instances where all non-zero capacities are uniform.
Recommendations
Cites work
- scientific article; zbMATH DE number 1559542 (Why is no real title available?)
- A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
- A 5-approximation for capacitated facility location
- A Best Possible Heuristic for the k-Center Problem
- A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
- A constant-factor approximation algorithm for the \(k\)-median problem
- A new greedy approach for facility location problems
- An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
- Analysis of a Local Search Heuristic for Facility Location Problems
- Approximating \(k\)-median with non-uniform capacities
- Approximating k-median via pseudo-approximation
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Centrality of trees for capacitated \(k\)-center
- Clustering to minimize the maximum intercluster distance
- Greedy Strikes Back: Improved Facility Location Algorithms
- How to Allocate Network Centers
- Improved Combinatorial Algorithms for Facility Location Problems
- Improved approximation algorithms for capacitated facility location problems
- Integer Programming and Combinatorial Optimization
- Local Search Heuristics for k-Median and Facility Location Problems
- On Representatives of Subsets
- The Capacitated K-Center Problem
- The design of approximation algorithms
Cited in
(30)- The capacitated single-source \(p\)-center problem in the presence of fixed cost and multilevel capacities using VNS and aggregation technique
- Generalized \(k\)-center: distinguishing doubling and highway dimension
- Capacitated covering problems in geometric spaces
- Connected \(k\)-center and \(k\)-diameter clustering
- On coresets for fair clustering in metric and Euclidean spaces and their applications
- Faster balanced clusterings in high dimension
- Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center
- The Euclidean \(k\)-supplier problem
- scientific article; zbMATH DE number 7758357 (Why is no real title available?)
- FPT approximation for capacitated clustering with outliers
- The distributed algorithms for the lower-bounded \(k\)-center clustering in metric space
- A constructive heuristic for the uniform capacitated vertex \(k\)-center problem
- Massively parallel and streaming algorithms for balanced clustering
- LP-based approximation for uniform capacitated facility location problem
- scientific article; zbMATH DE number 7651148 (Why is no real title available?)
- Improved approximation algorithms for capacitated fault-tolerant \(k\)-center
- Constant factor approximation algorithm for uniform hard capacitated knapsack median problem
- The fair \(k\)-center with outliers problem: FPT and polynomial approximations
- Iterative partial rounding for vertex cover with hard capacities
- The Capacitated K-Center Problem
- Integrality gaps for strengthened linear relaxations of capacitated facility location
- Improved bounds for metric capacitated covering problems
- Improved approximation algorithm for the distributed lower-bounded \(k\)-center problem
- Capacitated covering problems in geometric spaces
- Centrality of trees for capacitated \(k\)-center
- Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier
- Recent developments in approximation algorithms for facility location and clustering problems
- Bike rebalancing: how to find a balanced matching in the k center problem?
- New algorithms for fair \(k\)-center problem with outliers and capacity constraints
- Privacy preserving clustering with constraints
This page was built for publication: Centrality of trees for capacitated \(k\)-center
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896276)
