CS Paper Radar

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

Junho Hwang

cs.DS ·submitted 2026-10-27 13:12 UTC · v1
theory

Abstract

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.

Comment
24 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

The Online $k$-Taxi Problem Is Competitive on All Metrics

cs.DS ·2026-11-04 ·Christian Coester, Yichen Huang, Tze-Yang Poon
similarity 0.72
Abstract

The online $k$-taxi problem is a natural generalization of the $k$-server problem: $k$ taxis must serve a sequence of requests in a metric space. Each request is a pair of points $(r,s)$, and the algorithm serves the request by first moving a taxi to $r$ (to pick up a passenger) and then to $s$ (to drop off the passenger). The cost is the total distance traveled by the taxis without a passenger. Previous bounds for general $k$ all depended on the number of points $n$ or the aspect ratio $Δ$ of the metric space, both of which can be infinite on general metrics, and competitive algorithms were previously known on general metrics only for $k \le 3$. In this work, we give a $9^{k-1}$-competitive randomized algorithm against adaptive online adversaries and, as a corollary, an $81^{k-1}$-competitive deterministic algorithm for the online $k$-taxi problem.

0.10

The Harmonic Online $k$-Server Algorithm Is Poly(k)-Competitive

cs.DS ·2026-11-03 ·Yichen Huang
theory similarity 0.70
Abstract

The online $k$-server problem is one of the most fundamental problems in online algorithms. In this problem, $k$ servers are located in a metric space and serve a sequence of requests at points in the metric space by moving a server there. The Harmonic algorithm is a very natural algorithm: it chooses a server with probability inversely proportional to its distance from the request. It is also highly efficient, being memoryless and answering each request in $O(k)$ time. However, its competitive ratio has remained unsettled between the $O(2^k \log k)$ upper bound (Bartal and Grove, JACM 2000) and the $k(k+1)/2$ lower bound (Raghavan and Snir, 1994, IBM J. Res. Dev.). We prove that Harmonic is $2k^4$-competitive on every metric space against adaptive online adversaries. Our analysis uses a potential combining corrected electrical energy with the distances of online servers to their assigned adversary locations.

0.11

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

cs.DS ·2026-11-03 ·Tsubasa Harada
similarity 0.69
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

Metric Facility Location under Batched Random Order

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

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.66
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 Graph Coloring: Competitive Ratios Separating Randomized and Deterministic Algorithms

cs.DS cs.DMmath.CO ·2026-11-10 ·Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
theory similarity 0.64
Abstract

We study online coloring, focusing on the competitive ratio. The best previously known results were (1) a lower bound of $Ω(n / \log^2 n)$ for both deterministic and randomized algorithms by Halldórsson and Szegedy (1994), (2) an upper bound of $O(n / \log n)$ for randomized algorithms by Halldórsson (1997), and (3) an upper bound of $O(n / \log \log n)$ for deterministic algorithms by Kawarabayashi, Yoneda, and Yoneda (2025). In this paper, we improve these results as follows: 1. A new lower bound of $Ω(n / \log n)$ for deterministic algorithms. 2. A new upper bound of $O(n (\log \log n)^2 / \log^2 n)$ for randomized algorithms. 3. A new upper bound of $O(n / (\log \log n)^{2-\varepsilon})$ for deterministic algorithms for every fixed $\varepsilon>0$. For randomized algorithms, we nearly close the gap between the lower and upper bounds; the remaining gap is only $O((\log \log n)^2)$. We establish the asymptotic separation between randomized and deterministic online graph coloring. Against an oblivious adversary, a polynomial-time randomized algorithm achieves a competitive ratio asymptotically smaller than any deterministic algorithm can guarantee, even with unlimited computation.

0.17

Optimal analysis of Greedy for stochastic online Euclidean matching: flat torus to the rescue

cs.DS ·2026-09-20 ·Mingwei Yang, Sophie H. Yu
theory similarity 0.64
Abstract

We study online metric matching with $n$ servers and $n$ requests, all sampled independently and uniformly from $[0,1]^d$. We analyze the Greedy algorithm, which matches each arriving request to its closest available server. Despite its strong empirical performance, non-trivial bounds on Greedy's competitive ratio were previously known only for $d = 1$, where it is $O(1)$-competitive [BFP23]. We prove that Greedy is $O(1)$-competitive for every fixed $d\geq3$ and has competitive ratio $Θ(\sqrt{\log n})$ for $d=2$. Our proof first analyzes Greedy on the flat torus and then transfers the resulting estimates to the cube.

0.40

Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise

cs.LG ·2026-09-12 ·Xuan Li
theory similarity 0.64
Abstract

In the improving multi-armed bandits problem, each of $k$ arms has an unknown nondecreasing, discretely concave reward curve $f_i$, and pulling arm $i$ for the $t$-th time yields $f_i(t)$. For sufficiently long horizons, Blum and Ravichandran (ALT 2025) proved that randomized algorithms achieve an $O(\sqrt k)$ approximation to the best single arm when the scale $m=f^*(T)$ of the optimal arm is known ($T\ge2k$), and $O(\sqrt k\log k)$ when it is not ($T>4k$), against an $Ω(\sqrt k)$ lower bound. The logarithmic factor is unnecessary: a one-page \emph{probe-and-commit} algorithm achieves competitive ratio $4\sqrt3\,\sqrt k$ for $T\ge2\lfloor\sqrt k\rfloor$, without any knowledge of the scale, and we determine the optimal ratio for every horizon, $Θ(\sqrt k+k/T)$, also for unknown horizons. Without noise, \emph{no prior is needed at all}: a random-marginal probing algorithm reading neither the scale $m$, nor the concavity-envelope exponent $β$ of Blum, Garicano, Ravichandran and Sharma (UAI 2026), nor the horizon $T$, achieves the optimal $Θ(k^{β/(1+β)}+k/T)$ simultaneously for every $β$ and every horizon. Under the multiplicative noise model of Blum and Ravichandran, probe-and-commit keeps the same all-horizon order $Θ(\sqrt k+k/T)$ without knowing the noise level (and $Θ(\sqrt k)$ on the same range), but the price of priors jumps: for any fixed noise level $\varepsilon\in(0,1/2]$, the uniform price of adaptation $φ_\varepsilon(k)$ --- the worst case over horizons $T\ge16k$ of the loss relative to $k^{β/(1+β)}$ for algorithms knowing neither $m$ nor $β$ --- is $Θ_\varepsilon(\sqrt{\log k/\log\log k})$, the lower bound asymptotic in $k$ at fixed positive $\varepsilon$ and matched by a nested random-permutation probing algorithm, whereas knowing either $m$ or $β$ alone restores a constant price.

0.22