CS Paper Radar

Distance flexibility in spatial matching: the value of concentration

Taha Ameen, Sophie H. Yu

cs.DS math.PR ·submitted 2026-09-28 22:49 UTC · v1

Abstract

In spatial matching markets, a supply unit's flexibility is measured by its service radius, the maximum distance at which it can serve demand. In dimensions $k \geq 2$, we study how a platform should allocate service radii among the supply nodes subject to a budget on their sum. The platform makes this choice before observing supply and demand locations, with the objective of maximizing the expected fulfilled demand. We show that the shape of a preferred allocation depends on the total budget: under suitable conditions, large budgets favor allocations that are more uniform in the sense of majorization, while small budgets favor concentration. We also characterize a non-uniform allocation that is asymptotically optimal for a very-sparse regime, and show that the uniform allocation is suboptimal in this regime. Our results provide theoretical explanations for the radius allocation questions raised by the numerical experiments in [ASY26b].

Closest papers

Nearest neighbours by meaning across the whole index.

Online Transportation via Shifted Geometric Scales

cs.DS ·2026-11-12 ·John Jeang
theory similarity 0.62
Abstract · The majority of this work was generated and edited by iteratively prompting ChatGPT-6 Astra. After review, we believe the results to be corr…

In the Online Transportation problem, introduced by Kalyanasundaram and Pruhs (1995), requests arrive sequentially in a metric space and must be assigned immediately and irrevocably to one of $m$ facilities with available capacity. The objective is to minimize the total distance between requests and their assigned facilities. The problem generalizes the Online Metric Matching problem, in which each facility has unit capacity, and inherits a $2m-1$ lower bound on the competitive ratio for all deterministic algorithms. For Online Metric Matching, Kalyanasundaram and Pruhs (1993) and Khuller, Mitchell, and Vazirani (1994) established an optimal deterministic competitive ratio of $2m-1$, attained by the Retrospective (Permutation) algorithm. Kalyanasundaram and Pruhs (1998) conjectured that the same ratio is achievable for online transportation. Recently, Seth, Das, and Raghvendra (2026) obtained a competitive ratio of approximately $6.66m-2.89$ using their Robustified Greedy algorithm. We give an algorithm with competitive ratio $ρ(m-1)+1$, where $ρ\approx5.64$. Our algorithm builds on minimum-spanning-tree search techniques developed by Harada and Itoh (2025) and Arndt, Moseley, Pruhs, and Uetz (2026), using priority-based virtual depth-first searches over the known facilities. However our algorithm uses a phase to shift the geometric search scales, to decide when to skip certain searches and optimize the thresholds that define what edges to include in a given search.

0.14

Facility Location with Customer Incompatibilities

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

Optimality and Impossibility in Multidimensional Strategyproof Facility Location

cs.GT ·2026-10-27 ·Jianan Lin
theory similarity 0.59
Abstract

We study facility location in multidimensional normed spaces with the objective of minimizing social cost, the sum of agents' distances to their nearest facility. A deterministic mechanism selects $k$ facility locations based on the reports of $n$ agents and is strategyproof (SP) if no agent can reduce her distance by misreporting her location. We establish optimal approximation ratios and impossibility results. For a single facility in the Euclidean plane, we prove that the optimal approximation ratios among deterministic SP mechanisms are exactly those obtained by Goel and Hann-Caruthers [SCW 2023] for the coordinate-wise median (CM): $\frac{\sqrt{2(n^2+1)}}{n+1}$ for odd $n\ge3$ and $\sqrt{2}$ for even $n\ge4$. We remove the anonymity assumption from their optimality result. However, CM is not always optimal in non-Euclidean spaces: we give an SP mechanism that minimizes social cost exactly in $\ell_\infty^d$, whereas CM has a tight uniform approximation ratio of $2$ already in the plane. We then consider two facilities in $\ell_p$ spaces with $1<p<\infty$ and prove two impossibility results for every $n>2$. In the plane, no deterministic SP mechanism has a finite approximation ratio. In higher dimensions, the same impossibility holds for anonymous deterministic SP mechanisms. Finally, a reduction using distant agents and a limiting argument extends both impossibility results to every $k>2$ with $n>k$.

0.17

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

cs.GT ·2026-08-10 ·Mengfan Ma, Bo Peng
theoryhighly cited similarity 0.59
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

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.59
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

Randomized Strategyproof Facility Location: Two Facilities and Beyond

cs.GT ·2026-08-23 ·Hau Chan, Jianan Lin, Chenhao Wang
benchmark similarity 0.59
Abstract

We design and analyze randomized strategyproof mechanisms for multi-facility location under the utilitarian social-cost objective, the sum of the agents' distances to their nearest facilities. For two facilities, the Pairwise-Distance mechanism locates facilities at a pair of reported locations sampled with probability proportional to their distance. It is strategyproof on Ptolemaic spaces, including Euclidean and Hilbert spaces as special cases, and has an approximation ratio of \(4\). The resulting Hybrid-Distance mechanism is a fixed-probability mixture: it selects the classical Proportional mechanism [Lu et al., EC'10] with probability \(λ^*=\frac{5+4\sqrt3}{23}\) and Pairwise-Distance with probability $1-λ^*$. It is strategyproof on Ptolemaic spaces and has a tight approximation ratio of \(\frac{74+4\sqrt3}{23}\approx3.5186\), breaking the long-standing factor-\(4\) benchmark of [Lu et al., EC'10]. We complement the two-facility results by studying more facilities. First, for \(n\) agents and \(k=n-1\) facilities, we introduce the Inverse-Square mechanism, which omits one report with probability proportional to the inverse square of its nearest-neighbor distance and locates facilities at all remaining reports. It is strategyproof on any metric space and has an approximation ratio of \(Θ(\sqrt{n})\), improving the previous best-known ratio of \(\frac{n}{2}\) [Escoffier et al., ADT'11]. Second, for $k$ facilities on the line, we introduce the Gap-Product mechanism, which locates facilities at \(k\) reports and weights each set by the product of the gaps between consecutive selected reports. When \(k=3\), it is strategyproof and has a \(6\)-approximation, replacing the previous \(n\)-dependent guarantee [Fotakis and Tzamos, EC'13] by a constant, whereas it is not strategyproof for any \(k\ge4\).

0.43

Group-Fair Metric Distortion of Facility Assignment Problems

cs.GT ·2026-08-17 ·Alexandros A. Voudouris
similarity 0.58
Abstract

We study the group-fair distortion of metric facility assignment problems, where a set of agents, partitioned into unknown groups, must be assigned to a collection of facilities, possibly subject to capacity or other feasibility constraints. Given an assignment, each agent incurs a cost that depends on both its distance to its assigned facility and, via an affinity factor, the average distance of the other members in its group to their assigned facilities. We consider full-information algorithms, which have complete knowledge of the metric space, and ordinal-information algorithms, which know the distances between facilities and only the rankings of the agents over facilities (sorted by increasing distance). We establish worst-case distortion upper bounds in terms of the Max-of-Sum and Sum-of-Max social objectives, which combine the classic utilitarian and egalitarian social cost measures. We also derive informational lower bounds for one-sided matching and clustering, two fundamental and well-studied problems captured by our model, that match our upper bounds exactly for Max-of-Sum and asymptotically for Sum-of-Max.

0.23

Strategic Facility Location in Euclidean Spaces

cs.GT cs.DS ·2026-09-04 ·Kim Thang Nguyen, Lucas Perotin, Bertrand Simon
similarity 0.58
Abstract

The strategic facility location problem is defined as follows: $n$ agents report their location in a metric space, and the objective is to design a \emph{mechanism} deciding the (possibly randomized) location of a facility such that agents have no incentive to lie about their position. We focus on the egalitarian cost, which means that the goal of the mechanism is to minimize the expected maximal facility-agent distance. Meanwhile, mechanisms must be \emph{truthful} (or \emph{strategyproof}): no agent may decrease their expected distance to the facility via lying on their location. Designing truthful mechanisms minimizing the approximation ratio is a well-studied problem, and the optimal solution is known for the real line. We focus in this paper on higher dimension Euclidean spaces, for which gaps remain between the best known lower and upper bounds. We first show that, maybe counter-intuitively, the problem is easier for two agents on the plane rather than on the line: the mechanism can exploit the additional dimension to prevent more efficiently agent lies. Based on this intuition, we devise lower bounds for $\mathbb R^d$ asymptotically matching the best known approximation factor of $2$ for large $d$. We also provide novel mechanism ideas, improving over the best known algorithms on the plane, and when the agents belong to $\mathbb R^d$ but the facility may use an additional dimension.

0.03