CS Paper Radar

Exact-Quota Facility Location: A Transfer Framework and Three Approximation Guarantees

Hang Luo

cs.DS ·submitted 2026-11-13 14:57 UTC · v1
theory

Abstract

Facility location with outliers asks which facilities to open and which clients to serve, subject to a prescribed service quota. We give a framework for transferring facility-location cost certificates to this exact-quota setting. The framework yields deterministic polynomial-time approximation guarantees of $571/376<1.52$ for metric facility location with outliers, strictly less than $1.853$ for priority facility location with outliers, and $2.16995<2.17$ for squared-metric facility location with outliers. Each algorithm serves the prescribed number of clients and pays the original facility-opening costs. The framework separates initialization from improvement. A growth process is stopped when it first reaches the quota; deleting excess clients from its last batch leaves a payment deficit supported on a bounded number of facilities. Greedy additions then reoptimize the served client set. A threshold-coverage representation makes the resulting service cost supermodular and allows the usual density analysis to compare different client sets. Finally, enumerating and prepaying a constant number of expensive facilities absorbs the exceptional costs. A transfer theorem states exactly which initialization certificate is sufficient and how many prepaid facilities it requires. The three applications supply this certificate in different ways. The metric case uses a quota prefix of reassigning JMS; the priority case uses persistent contributions and a cleanup ordered by service level; and the squared-metric case uses a local factor-revealing certificate valid for arbitrary client subsets of the same run. We provide complete finite proofs of the numerical interfaces, including an exact rational certificate for the squared-metric bound.

Comment
24 pages. Includes an exact rational certificate and a solver-free verifier as ancillary files

Closest papers

Nearest neighbours by meaning across the whole index.

A Constant-Factor Approximation for Capacitated Facility Location with Outliers

cs.DS ·2026-11-03 ·Rajni Dabas
similarity 0.76
Abstract

We give a deterministic polynomial-time $(60/11+\eps)$-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+\eps$ 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 \cite{BGG18} 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+\eps)$-approximation; starting each penalty run from the preceding solution improves the guarantee to $60/11+\eps$.

0.06

Facility Location with Customer Incompatibilities

cs.DS ·2026-10-31 ·Zachary Friggstad, Pengfei Wu
similarity 0.70
Abstract

We study metric facility location with customer incompatibilities, where the clients assigned to each facility must satisfy prescribed independence constraints. We first consider the setting of facility-opening costs and where there is a single matroid $\mathcal M$ over the clients and the set of clients assigned to an open facility must be an independent set in $\mathcal M$. We develop a polynomial-time \((1+\sqrt{2}+ε)\)-approximation algorithm for this setting. We further obtain a polynomial-time \((15+ε)\)-approximation algorithm for the case of non-uniform facility-opening costs when $\mathcal M$ is a partition matroid that only permits $b_g$ clients to be assigned to a facility for each group $g$ in the partition. Both settings are substantial generalizations of Capacitated Facility Location with uniform capacities. Our algorithms are based on local search using add, delete, and single-swap operations. As with CFL, bounding the connection cost is reasonably straightforward using supermodularity of the minimum connection-cost function. However, bounding the facility opening costs requires novel arguments in both cases. We use a ``compression'' argument based on matroid exchange principles to identify a subset of the locally opened facilities whose size is no larger than that of an optimal facility set. The opening costs of facilities outside this subset can be bounded using supermodularity, while bounding the costs of the remaining facilities requires different arguments. It is natural to consider a variant where each possible facility $i$ has its own matroid $\mathcal M_i$ defining the subsets of clients it can feasibly serve. We also show problem is at least as hard to approximate as Set Cover even if all $\mathcal M_i$ are partition matroids that have the same partition of clients, just different group bounds $b_g$.

0.18

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

cs.DS ·2026-10-30 ·Zachary Friggstad, Pengfei Wu
similarity 0.69
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.

0.53

Individually Fair Facility Location

cs.DS cs.CC ·2026-11-12 ·Rajni Dabas, Samir Khuller, Milind Maiti
code/data similarity 0.67
Abstract

We study individually fair facility location, where each client must connect to an open facility within a prescribed radius and the objective is to minimize total opening and connection cost. We show that preserving the radii changes the approximability of metric facility location fundamentally. For every fixed radius violation below three, no deterministic polynomial-time algorithm achieves a sublogarithmic cost factor unless $\mathrm{P}=\mathrm{NP}$. The hardness holds with uniform opening costs and uniform radii. It contradicts the strict-fairness constant-factor guarantee recently claimed by Liu, Xu, and Zhang [Theory of Computing Systems, Vol. 70 (2026)]. We then establish a positive result for arbitrary client radii. We give a randomized polynomial-time algorithm that has cost at most $1.725$ times the strictly fair optimum and serves every client within three times its fair radius (in the Appendix we show how this can be de-randomized). We use the approach of Byrka, Srinivasan and Swamy [IPCO 2010]. The facility-location radius factor three is therefore optimal among deterministic polynomial-time algorithms with constant cost factor, unless $\mathrm{P}=\mathrm{NP}$. Experiments on real-world data indicate that the worst case radius bound is rarely realized in practice: the algorithm serves over 99.8% of clients within their stated radius, and never beyond 1.5 times it. Our code is available at https://github.com/milindmaiti/IFFL_Implementation.

0.33

Iterative Randomized Rounding for $k$-Median in General and Euclidean Metrics

cs.DS ·2026-10-22 ·Jarosław Byrka, Yuhao Guo, Yang S. Hu, Shi Li, Yongho Shin +3 more
similarity 0.63
Abstract · 76 pages, 1 figure. The abstract was abridged to meet the arXiv requirement

We refine the iterative rounding framework of Byrka, Guo, Hu, Li, Wan, and Wang [FOCS'26], which gives a $(2+\varepsilon)$-approximation for $k$-median. Our algorithm opens $k+O(1)$ facilities with expected connection cost at most $1.9999$ times the standard LP value. Despite the small numerical gain, this shows that the LP integrality gap is below $2$ with a constant additive facility allowance, partially answering Li and Svensson's open question [SICOMP'16]. Their reduction yields a $1.9999$-approximation opening at most $k$ facilities. Our preprocessing makes the LP solution $\mathrm{poly}(\varepsilon)$-integral with a $(1+\varepsilon)$ loss in each client's expected connection cost and $O(1)$ extra facilities, without special treatment of clients with concentrated fractional facilities. We replace batch processing with single-facility openings and combine a tighter analysis for clients with unequal distances to their facilities with a complementary algorithm for nearly uniform distances. In Euclidean metrics, we obtain a $1.71955$-approximation for $k$-median and a $1.4561$-approximation for uncapacitated facility location (UFL). For every $p\ge2$ and sufficiently small $\varepsilon>0$, we obtain a $((3^p+2)/3+\varepsilon)$-approximation for $k$-clustering with $p$-th power distance costs. For $p=2$, our $(11/3+\varepsilon)$-approximation for $k$-means improves the $(3+\ln2+\varepsilon)$ bound of Anand, Charikar, Cohen-Addad, Gao, Grandoni, Lee, Sharma, and van Wijland [SODA'27]. The Euclidean $k$-median, $k$-means, and UFL ratios are below the respective general-metric hardness bounds $1+2/e$, $1+8/e$ [STOC'02], and $1.463$ [J. Algorithms'99]. The Euclidean $k$-median bound relies on a geometric inequality proved via a nonnegativity certificate constructed from positive-semidefinite kernels.

0.14

Metric Facility Location under Batched Random Order

cs.DS ·2026-11-03 ·Fabrizio Grandoni, Stefano Leonardi, Matteo Russo
theory similarity 0.59
Abstract

We study online metric facility location in the batched random-order model. An adversary partitions $n$ clients into $B$ nonempty batches, which arrive in uniformly random order. Each batch is revealed in full, and its clients must be connected to open facilities before the next batch arrives. Openings and assignments are irrevocable, and the objective is to minimize the total opening and connection cost. For both uniform and nonuniform opening costs, we prove that the tight competitive ratio is \[ Θ\!\left(\min\left\{\log(B+1), \sqrt{\log(n-B+2)}\right\}\right). \] Thus, the ratio is constant both when there is a single batch and when every batch is a singleton, but intermediate numbers of batches can require a $Θ(\sqrt{\log n})$ ratio. Our algorithms build on Meyerson's algorithm (2001) and do not need to know $n$ nor $B$. A key algorithmic novelty is that we process the clients in a batch one by one in uniform random order (hence neglecting the global properties of the batch). We present a novel analysis of this algorithm that hinges on the random order of the batches, as well as of the clients within each batch. We also provide a matching competitive ratio lower bound already for uniform costs, and even when the entire metric is known in advance.

0.21

Settling the Approximability of Submodular Facility Location

cs.DS ·2026-10-13 ·Adam N. Elmachtoub, Bento Natura, Meike Neuwohner
theory similarity 0.59
Abstract

In submodular facility location (SFL), introduced by Svitkina and Tardos (SODA 2006), clients $\mathcal{C}$ in a metric space are assigned to facilities $\mathcal{F}$. A facility serving a set $S \subseteq \cal C$ of clients incurs cost $g(S)$, where $g$ is a monotone submodular function common to all facilities. The best known approximation factor for SFL is $O(\log\log|\mathcal{C}|)$, due to Abbasi, Adamczyk, Bosch-Calvo, Byrka, Grandoni, Sornat, and Tinguely (ICALP 2024), improving on the $O(\log|\mathcal{C}|)$-approximation of Svitkina and Tardos. We show that this is best possible up to a constant factor in the value-oracle model by showing that there exists no algorithm with only polynomially many queries to $g$ with approximation ratio $o(\log\log|\mathcal{C}|)$. This bound holds for algorithms with unlimited computation time, and when $g$ is restricted to matroid rank functions. We also show that the natural linear programming relaxation has an integrality gap of $Θ(\log\log|\mathcal{C}|)$. Our lower bound follows by constructing an extension of Vondrák's symmetry-gap approach (FOCS 2009) for matroid rank functions.

0.36

Truthful Two-Facility Location with Candidate Locations in Metric Spaces

cs.GT ·2026-10-13 ·Panagiotis Kanellopoulos, Alexandros A. Voudouris
theory similarity 0.58
Abstract

We study a truthful facility location problem in which agents have private positions in a metric space and known approval preferences over two distinct facilities. Each agent incurs a cost equal to her total distance from the facilities she approves. The goal is to locate the facilities at a given set of candidate locations so as to approximately minimize either the social cost or the max cost, while incentivizing the agents to report their positions truthfully. This problem was previously studied for line metrics and deterministic mechanisms. We first settle the approximation ratio of deterministic mechanisms for the social cost on the line by establishing a lower bound of $7$, matching the upper bound from previous work, and show that randomization leads to a strict improvement. For the max cost, we show that the previously known optimal deterministic guarantee of $3$ remains tight even for universally strategyproof mechanisms. We then turn to general metric spaces. For deterministic strategyproof mechanisms, we obtain tight approximation ratios of $2n-1$ for the social cost and $5$ for the max cost. We also show that randomization yields substantial improvements for both objectives: for the social cost, we obtain a tight characterization, while for the max cost we establish nearly matching upper and lower

0.04