CS Paper Radar

Metric Facility Location under Batched Random Order

Fabrizio Grandoni, Stefano Leonardi, Matteo Russo

cs.DS ·submitted 2026-11-03 13:58 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Tight Bounds on the Cost of Adaptivity for the Meyerson Sketch

cs.DS ·2026-09-06 ·Edith Cohen, Elena Gribelyuk, Pasin Manurangsi, Uri Stemmer
similarity 0.68
Abstract

In online facility location, points arrive one at a time, and the algorithm must either open a facility at the arriving point or route the point to an existing facility. The Meyerson sketch opens a facility at each arriving point with probability proportional to the point's distance to the closest open facility, and requires no state beyond the set of open centers. Due to its simplicity, space efficiency, and strong guarantees against the offline optimum, the Meyerson sketch has become a workhorse of streaming and online clustering. In many such applications, however, the set of open facilities are visible to the process that generates the stream, which can adaptively select future points based on the algorithm's past random choices, voiding its classical guarantees. In this work, we quantify the effect of such adaptivity. We compare an adaptively generated run of the sketch against an \emph{oblivious replay}, an independent execution, with fresh coins, on the very same generated sequence, and study the \emph{adaptivity ratio} of expected adaptive cost to expected replay cost. We determine the worst-case ratio in both directions: adaptivity can neither inflate nor deflate the expected cost, or the number of open facilities, by more than an $O(\logΔ/\log\logΔ)$ factor, where $Δ$ is the aspect ratio of the input points (the ratio of the largest to the smallest pairwise distance). This is asymptotically tight as there are deterministic generators on the real line that inflate or deflate the cost by an $Ω(\logΔ/\log\logΔ)$ factor. We show that these robustness guarantees carry over to Meyerson-based sketches for approximate $k$ clustering with sketch size $O(k\,\mathrm{polylog}(n))$.

0.19

Tight Bounds for Randomized Generalized $k$-Server on Uniform Metrics

cs.DS ·2026-10-27 ·Junho Hwang
theory similarity 0.67
Abstract · 24 pages, 3 figures

In the generalized $k$-server problem, each of $k$ servers moves in its own metric space, and a request $(r_1,\dots,r_k)$ is served once some server $i$ stands at the point $r_i$ of its space. We determine the randomized competitive ratio against an oblivious adversary when every space is a uniform metric. With unit distances the ratio is $Θ(k\log k)$: we give a $(k+1)\ln(2k)$-competitive algorithm and show that for large $k$ every algorithm has ratio at least $\frac{1}{20}k\ln k$, improving the bounds $O(k^2\log k)$ and $Ω(k)$ of Bienkowski, Jeż, and Schmidt. When server $i$ pays $w_i$ per move, the ratio is $\exp(Θ(k))$: we give a $20^k$-competitive algorithm, which also applies to weighted $k$-server on uniform metrics. This improves the $\exp(O(k^2))$ bound of Bijoy, Mondal, and Chiplunkar and matches the $Ω(2^k)$ lower bound of Ayyadevara and Chiplunkar up to the base of the exponent. Both algorithms follow normalized weights exactly, through couplings whose expected movement is controlled by the decrease of the logarithm of the total weight. The lower bound hides a random permutation among the solutions of random permutation constraints, which split into small, well-separated components, and then forbids one position to one server at a time.

0.34

Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness

cs.DS ·2026-09-18 ·Anish Hebbar, Ravi Kumar, Roie Levin, Joseph, Naor +1 more
similarity 0.67
Abstract

Suppose an online algorithm is given an unbiased $p$-sample of its input as offline advice; can the algorithm exploit the sample to achieve beyond-worst-case performance? We study this online algorithms with a sample (OAS) model. We show a tight $O\left(\log (1/p) \cdot \log m + \log n\right)$-competitive algorithm for set cover, exponentially improving upon the $O\left(1/p \cdot \log (mn)\right)$ guarantee of Gupta et al. (SODA'24) and answering an open question therein. Our techniques extend to covering integer programs and non-metric facility location, also yielding tight bounds for these problems. Further, we give an $O(\log (1/p)/ \log \log (1/p))$-competitive algorithm for metric facility location, answering an open question of Argue et al. (NeurIPS'22). We then introduce and study the robust variant of the OAS model, in which an adversary is allowed to arbitrarily modify $k$ elements of the $p$-sample. For set cover, covering integer programs, and non-metric facility location, we obtain a tight competitive ratio of $O\left(\log (k/p) \cdot \log m + \log n\right)$. For metric facility location and Steiner tree, we obtain tight competitive ratios of $O\left(\log (k/p) / \log \log (k/p) \right)$ and $O\left(\log (k/p)\right)$ respectively. To the best of our knowledge, these are the first results for robust algorithms in the OAS setting.

0.19

Online Metric Matching with Unknown i.i.d. Arrivals

cs.DS ·2026-11-03 ·Tsubasa Harada
similarity 0.66
Abstract · 14 pages

We study online metric matching with $n$ servers and $n$ requests drawn independently from an unknown distribution. Each request must be matched immediately and irrevocably to an unused server, and the algorithm receives no samples before the process starts. We give a randomized algorithm that is $O((\log\log\log n)^2)$-competitive on arbitrary metric spaces and $O(1)$-competitive on tree metrics. These guarantees match the corresponding bounds for known i.i.d. request distributions in [GGPW19] up to constant factors. More generally, our competitive ratio is $O(α(n))$ whenever the Fair-Bias algorithm introduced in that work has competitive ratio $α(n)$ for known i.i.d. arrivals on the same class of metrics. Consequently, proving that Fair-Bias is constant-competitive on general metrics would also yield a constant-competitive algorithm for unknown i.i.d. arrivals.

0.18

Optimal High Probability Bounds for Random Order Online Sorting

cs.DS ·2026-10-11 ·Chenglin Fan, Mingyu Kang
theory similarity 0.66
Abstract · 46 pages

In random order online sorting, a fixed multiset of $n$ real numbers arrives in a uniformly random order. Each value must be placed immediately and irrevocably into an empty position of an array with exactly $n$ positions. The objective is to minimize the sum of the absolute differences between consecutive entries. If the entire input were known in advance, sorting the values would be optimal and would have cost equal to the range of the input. We prove that the optimal worst case competitive ratio in this model is $Θ(\log n)$ with high probability. In particular, we give a single online algorithm that achieves an $O(\log n)$ competitive ratio with high probability for every fixed input, and we show that every randomized online algorithm has some fixed input on which an $Ω(\log n)$ ratio is unavoidable with high probability. The same upper bound also holds for independent samples from an arbitrary unknown distribution on the real line. The algorithm uses the random arrival order to learn the relative positions of future values from the values seen so far. It maintains a hierarchy of small regions of the input order and allows an arriving value to use nearby space when its preferred region is full. This flexibility avoids the need to reserve large amounts of space for unlikely local fluctuations. The analysis shows that large displacements become rapidly less likely as their scale grows, leading to the $O(\log n)$ high probability bound. A matching lower bound shows that no randomized online algorithm can improve the logarithmic dependence in the worst case.

0.23

Anchoring for Truthfulness: The Random-Anchor Volume Mechanism for Multi-Facility Location

cs.GT ·2026-08-17 ·Haris Aziz, Simon Mackenzie, Mashbat Suzuki
theory similarity 0.66
Abstract

We study the strategyproof placement of \(k\) facilities on the real line for \(n\) agents who privately report their locations, without monetary transfers. For two facilities, the Proportional Mechanism of Lu, Sun, Wang, and Zhu (2010) is strategyproof in expectation and achieves a constant-factor approximation to the optimal social cost. Whether such a guarantee is possible for three facilities in the standard model, where each agent is served by her nearest open facility, has remained open. We resolve this question affirmatively by introducing the \emph{Random-Anchor Volume} mechanism. The mechanism first opens a facility at the report of a uniformly random agent, called the \emph{anchor}, and then jointly selects two additional reports, assigning each pair probability proportional to the product of the two consecutive gaps formed by the pair and the anchor. We prove that the mechanism is strategyproof in expectation and has expected social cost at most \(8 OPT_3\), where \(OPT_k\) denotes the minimum social cost achievable using at most \(k\) facilities. The mechanism naturally extends to every \(k\geq 2\) by selecting \(k-1\) additional reports with probability proportional to the product of the consecutive gaps among them and the anchor. Under truthful reporting, this generalization has expected social cost at most \(4(k-1)OPT_k\). Its incentive guarantee, however, has a sharp boundary: the mechanism is strategyproof in expectation for \(k\in\{1,2,3\}\), but is manipulable for every \(k\geq 4\).

0.44

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

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

Exact and Asymptotic Analysis of Greedy Online Facility Assignment on Cycle Metrics

cs.DS ·2026-10-11 ·Md. Tanzeem Rahat, Md. Rawha Siddiqi Riad, Md. Manzurul Hasan
theory similarity 0.64
Abstract

We identify the free-facility gaps of greedy online assignment on a cycle with the discrete additive coalescent and use this connection to determine the exact expected assignment cost. The cycle has circumference $n$, with one unit-capacity facility at each integer point and $n$ independent uniform arrivals. Each request is assigned immediately to a nearest free facility. The conditional one-step cost is the sum of squared gap lengths divided by $4n$. A uniform cyclic-order argument identifies the unordered gap process with additive coalescence. The classical Cayley-tree representation then reduces the accumulated cost to a two-vertex distance functional, yielding \[ G_n=\frac n4\sum_{d=0}^{n-1}\prod_{j=1}^{d}\left(1-\frac jn\right) \sim\frac14\sqrt{\frac\pi2}\,n^{3/2}. \] The formula requires a linear number of scalar recurrence steps to evaluate. We also obtain an asymptotic upper bound of $π\sqrt3/2$ on the ratio of expected greedy cost to expected offline optimum under this arrival model. An exact rational Bellman calculation shows that greedy is optimal for three facilities but exceeds the optimal online expected cost by $1/512$ for four facilities. Independent exact recurrences and finite tree enumeration provide reproducible checks of the analysis.

0.28