A Constant-Factor Approximation for Capacitated Facility Location with Outliers
cs.DS
Submitted: 2026-11-03
Updated: 2026-11-03
License: http://creativecommons.org/licenses/by/4.0/
The gist: We give a deterministic polynomial-time (60/11+) -approximation for metric capacitated facility location with outliers, with arbitrary opening costs and nonuniform hard capacities.
Abstract
We give a deterministic polynomial-time (60/11+) -approximation for metric capacitated facility location with outliers, with arbitrary opening costs and nonuniform hard capacities. The algorithm respects both capacities and the outlier budget. Its guarantee, approximately 5.455, is close to the best known factor 5+ for capacitated facility location without outliers. The main ingredient is a local-search comparison for a common rejection penalty that retains the signed difference between the algorithm's and the comparator's rejection counts. Ordinary approximation guarantees for the penalty objective do not provide this comparison. We extend the exchange-forest accounting of Bansal, Garg, and Gupta so that a nonnegative assignment remainder pays for rejection and cancels in the final bound. We then merge two penalty assignments whose served counts bracket the outlier quota. Grouping alternating paths by their terminal facility preserves capacities and shares opening costs. These ingredients give a (20/3+) -approximation; starting each penalty run from the preceding solution improves the guarantee to 60/11+.
Sources
- Locating Charging Stations: Connected, Capacitated and Prize- Collecting
- Multiple Swap Local Search Approximations for Uniform-Cost Capacitated Facility Location with Extensions to Outliers
- Approximation algorithms for Capacitated Facility Location Problem with Penalties
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles