CS Paper Radar

Individually Fair Facility Location

Rajni Dabas, Samir Khuller, Milind Maiti

cs.DS cs.CC ·submitted 2026-11-12 01:02 UTC · v1
code/data

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Facility Location with Customer Incompatibilities

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

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

cs.DS ·2026-11-13 ·Hang Luo
theory similarity 0.67
Abstract · 24 pages. Includes an exact rational certificate and a solver-free verifier as ancillary files

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.

0.24

Truthful Two-Facility Location with Candidate Locations in Metric Spaces

cs.GT ·2026-10-13 ·Panagiotis Kanellopoulos, Alexandros A. Voudouris
theory similarity 0.64
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

A Constant-Factor Approximation for Capacitated Facility Location with Outliers

cs.DS ·2026-11-03 ·Rajni Dabas
similarity 0.62
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

Breaking the 4-Approximation Barrier in Strategyproof Two-Facility Location

cs.GT ·2026-08-10 ·Mengfan Ma, Bo Peng
theoryhighly cited similarity 0.61
Abstract · 23 pages, 1 figure

We study strategyproof mechanism design without transfers for the two-facility location problem in metric spaces. A mechanism selects two facility locations based on agents' reported locations; each agent incurs her distance to the nearer facility, and the objective is to minimize the expected social cost. A mechanism is strategyproof if no agent ever benefits from misreporting her location. The best approximation ratio achieved by a randomized strategyproof mechanism has been $4$, attained by the Proportional mechanism of Lu, Sun, Wang, and Zhu (EC 2010), and the best lower bound has been $1.045$, due to Lu, Wang, and Zhou (WINE 2009). Neither bound has moved since then, even on the line $\mathbb{R}$. We improve both bounds. Our main result is a randomized strategyproof mechanism with approximation ratio $11/3 \approx 3.667$ on every Ptolemaic metric space, a rich class containing all Euclidean spaces. The mechanism randomizes between the Proportional mechanism and a new mechanism that we call Global Pair. Global Pair draws an unordered pair of agents with probability proportional to their distance and opens facilities at their reported locations. Although Global Pair and Proportional each have approximation ratio $4$, the two mechanisms attain their worst-case approximation ratios on complementary instances. Randomizing between them balances these complementary weaknesses and breaks the $4$-approximation barrier. On the lower-bound side, we construct a new two-profile instance that yields a lower bound of $(1+\sqrt{2})/2 \approx 1.207$, improving upon the previous lower bound of $1.045$.

0.50

Metric Facility Location under Batched Random Order

cs.DS ·2026-11-03 ·Fabrizio Grandoni, Stefano Leonardi, Matteo Russo
theory similarity 0.61
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

Constant-Factor Approximation for Capacitated Clustering in Low Dimension with $(1+ε)k$ Centers

cs.CG cs.DS ·2026-10-29 ·Kangke Cheng, Guanlin Mo, Hu Ding
similarity 0.60
Abstract

In many applications of $k$-median and $k$-means, including load balancing and redistricting, each center can serve only a bounded number of clients. This leads to capacitated clustering, in which a client may be forced to use a distant center because all nearby ones are full. This loss of locality defeats the techniques behind approximation schemes, and no constant-factor approximation is known in general metrics even for capacitated $k$-median. A long line of work therefore opens $K=k+\lfloorεk\rfloor$ centers for a fixed $ε\in(0,1]$, while respecting the capacities exactly. We give a deterministic polynomial-time algorithm for uniform soft capacities in low dimension, that is, when the clients or the center locations have bounded doubling dimension. With $K$ centers, its ratio is $3-2ε$ for $k$-median and $9-8ε$ for $k$-means, or $5-4ε$ in $\mathbb{R}^d$. Apart from $k$-median in the plane, these are the first polynomial-time ratios bounded by a constant independent of $ε$; previously, the best ratio was $O(ε^{-2}\log(1/ε))$, even for $k$-median. We also obtain ratios that stay bounded as $ε\to0$ for non-uniform and hard capacities in low dimension, and ratios polylogarithmic in $1/ε$ in general metrics. Our approach starts from a simple structural observation: a near-optimal uncapacitated solution can be split into fewer than $2k$ capacity-respecting blocks, so $2k$ centers already suffice, one per block. Our main tool, the rescue lemma, shows that once every block that sends clients to a center of the optimal solution is rescued (given a private center), that center can be closed, so each extra center effectively rescues about two blocks. This lets $\lfloorεk\rfloor$ extra centers rescue nearly an $ε$-fraction of the blocks, yielding the linear dependence on $ε$ in our ratios.

0.16

Optimally Selecting Representative Agents from a Metric Space

cs.GT cs.LG ·2026-08-29 ·Benjamin Cookson, Eva Deltl, Yeeseok Oh
theory similarity 0.59
Abstract

This paper studies the problem of proportionally fair clustering, where the goal is to select $k$ ``centers'' from a metric space that fairly represent a set of agents who also lie in the metric space. Specifically, we focus on finding a clustering satisfying a fairness property known as the Droop core. In the practical special case in which the set of feasible center locations contains every agent location, the previous best-known result guaranteed a $(1 + \sqrt{2})$-approximation of the Droop core, while the best-known lower bound was $2$. In this paper, we show that this lower bound is tight and that a clustering in the $2$-Droop core always exists. Further, we show that such a clustering can be achieved by only selecting centers from locations in the metric space where an agent resides. We establish this using Scarf's theorem guaranteeing a nonempty core for balanced non-transferable utility games. This result has several interesting corollaries. Most notably, it resolves the $β$-plurality problem of Aronov et al. [2021] for general metric spaces. The main result of this paper was generated by $\mathtt{ChatGPT}$-$\mathtt{5.6}$-$\mathtt{Sol}$ through a series of interactions with the authors. The authors of this paper verified the generated proof and rewrote it for clarity.

0.27