paper

Multiple Swap Local Search Approximations for Uniform-Cost Capacitated Facility Location with Extensions to Outliers

arXiv:2610.41187

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 -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 -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 -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 -approximation, again by Dabas, Garg, and Gupta. Finally, we show that the factor 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.