arXiv preprint ·
Multiple Swap Local Search Approximations for Uniform-Cost Capacitated Facility Location with Extensions to Outliers
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study \textsc{Capacitated Facility Location}, a fundamental clustering problem, in the setting of uniform opening costs and non-uniform capacities. We give a polynomial-time $(3+ε)$-approximation for this problem. Our algorithm is a multiple-swap generalization of the local search algorithm by Dabas, Garg, and Gupta (2024), who obtained a $3.732$-approximation. The main technical contribution is the analysis of this natural multiple-swap local-search method: variants of this approach have been analyzed previously, but allowing larger swaps requires new grouping and counting arguments. We also show that a multiple-swap local search algorithm provides a $(3+ε)$-approximation for \textsc{Capacitated Facility Location with Outliers}, again in the same setting of uniform opening costs and non-uniform capacities. This is an improvement over the $6.372$-approximation, again by Dabas, Garg, and Gupta. Finally, we show that the factor $3$ is tight for our local-search framework, and that the same multiple-swap idea does not improve the known locality gap for the non-uniform opening-cost setting.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
The Competitive Ratio of Online Budgeted Allocation is Strictly Smaller than $1-1/e$
Limits and Constants of OpenAI's Claimed ETH Refutation
Traveling Salesman Problem on Graphs with Proportional Independent Set
Facility Location with Customer Incompatibilities
Compressed Oracle Duality: A simple framework for knowing what quantum adversaries know
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.