Centrality of trees for capacitated k-center
From MaRDI portal
Publication:896276
DOI10.1007/S10107-014-0857-YzbMATH Open1337.90036arXiv1304.2983OpenAlexW2114589083MaRDI QIDQ896276FDOQ896276
Authors: Hyung-Chan An, Aditya Bhaskara, Chandra Chekuri, Shalmoli Gupta, Vivek Madan, Ola Svensson 
Publication date: 9 December 2015
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1304.2983
Recommendations
approximation algorithmscapacitated \(k\)-center problemcapacitated network location problemsLP-rounding algorithms
Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25) Discrete location and assignment (90B80)
Cites Work
- The design of approximation algorithms
- Approximating k-median via pseudo-approximation
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Greedy Strikes Back: Improved Facility Location Algorithms
- Title not available (Why is that?)
- Clustering to minimize the maximum intercluster distance
- A Best Possible Heuristic for the k-Center Problem
- How to Allocate Network Centers
- The Capacitated K-Center Problem
- On Representatives of Subsets
- Improved approximation algorithms for capacitated facility location problems
- A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
- Improved Combinatorial Algorithms for Facility Location Problems
- A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
- A 5-approximation for capacitated facility location
- A new greedy approach for facility location problems
- Integer Programming and Combinatorial Optimization
- An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
- Local Search Heuristics for k-Median and Facility Location Problems
- Analysis of a Local Search Heuristic for Facility Location Problems
- A constant-factor approximation algorithm for the \(k\)-median problem
- Centrality of Trees for Capacitated k-Center
- Approximating \(k\)-median with non-uniform capacities
Cited In (29)
- Improved approximation algorithms for capacitated fault-tolerant \(k\)-center
- Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems
- Bike rebalancing: how to find a balanced matching in the k center problem?
- Massively parallel and streaming algorithms for balanced clustering
- Iterative partial rounding for vertex cover with hard capacities
- On coresets for fair clustering in metric and Euclidean spaces and their applications
- Title not available (Why is that?)
- A constructive heuristic for the uniform capacitated vertex \(k\)-center problem
- Constant factor approximation algorithm for uniform hard capacitated knapsack median problem
- Capacitated Covering Problems in Geometric Spaces
- Generalized \(k\)-center: distinguishing doubling and highway dimension
- The capacitated single-source p-center problem in the presence of fixed cost and multilevel capacities using VNS and aggregation technique
- Integrality gaps for strengthened linear relaxations of capacitated facility location
- Faster balanced clusterings in high dimension
- Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center
- Title not available (Why is that?)
- Connected \(k\)-center and \(k\)-diameter clustering
- Improved approximation algorithm for the distributed lower-bounded \(k\)-center problem
- LP-based approximation for uniform capacitated facility location problem
- Title not available (Why is that?)
- FPT approximation for capacitated clustering with outliers
- The distributed algorithms for the lower-bounded \(k\)-center clustering in metric space
- Improved bounds for metric capacitated covering problems
- Capacitated covering problems in geometric spaces
- The fair \(k\)-center with outliers problem: FPT and polynomial approximations
- Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier
- The Euclidean k-Supplier Problem
- The Capacitated K-Center Problem
- New algorithms for fair \(k\)-center problem with outliers and capacity 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)
