CS Paper Radar

A Deterministic Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving

Ian D'Ambrosio

cs.DS cs.LG ·submitted 2026-08-15 03:51 UTC · v2
theory

Abstract

Dynamic Mixture-of-Experts Serving allocates k replica GPUs among m experts as workloads change. At each round, the online algorithm sees the current workload, chooses integral replica counts, and pays bottleneck service cost plus replica movement. It does not know future workloads. Huang, Lou, and Xiao gave an O(sqrt(log k))-competitive randomized algorithm for this problem. We prove a deterministic O(1)-competitive algorithm. For every number of experts and every k>=1, the algorithm satisfies ALG_det <= 10 C_PB OPT + (5 C_PB + 8) k + 16, where C_PB is the absolute constant from Chasing Positive Bodies at resource augmentation one and covering sparsity two. Consequently, CR_det(k)<=10 C_PB for every k>=1, so CR_det(k)=Theta(1). The multiplicative factor does not depend on the number of experts, replica budget, horizon, or workload values. Thus randomization is not needed for the asymptotic guarantee. The proof has two layers. A finite tangent envelope, summable positive resets, and a nonexpansive balanced projection reduce reciprocal-max service costs to a deterministic exact-budget fractional path. A new deterministic rounding theorem converts every such path to integral allocations with service distortion three and movement bounded by the fractional movement plus 6k. The complete reduction, rounding theorem, causal composition, and quantified main theorem are machine-checked in Lean 4 relative to the positive-body result as the sole scientific source premise. The theorem concerns the allocation model above. It does not include network topology, shared-edge congestion, or routing decisions.

Comment
10 pages. This revision replaces the randomized integral bound with a deterministic constant-competitive theorem. Reproducibility archive: doi:10.5281/zenodo.22119372

Closest papers

Nearest neighbours by meaning across the whole index.

A Tight Linear Deterministic Competitive Ratio for Fully Online KV-Cache Scheduling

cs.DS ·2026-08-14 ·Ian D'Ambrosio
theory similarity 0.63
Abstract · 6 pages. The exact fully online model, fixed-memory-before-scheduler quantifier order, serial upper bound, and wide-short lower bound are ch…

Jaillet et al. introduced a fully online model for batching nonpreemptive LLM requests under a growing KV-cache memory constraint. For total end-to-end latency they proved that every deterministic algorithm has competitive ratio Omega(sqrt(n)), while the elementary sequential upper bound is n. We close this gap. Let R_det(n,M) be the optimal deterministic ratio for exactly n requests at memory M, and let R_det(n)=sup_M R_det(n,M). For every n >= 2 we prove (n-1)/12 <= R_det(n) <= n, so R_det(n)=Theta(n). The lower bound releases one memory-filling long request, observes its deterministic start time, and then releases n-1 wide one-token requests halfway through the long run. No short request can overlap the long one, whereas a hindsight schedule runs the two groups in the opposite order when useful. The hard instance uses the explicit fixed memory M=2(n-1)n. The upper bound is achieved by a uniform causal serial policy. The exact model, causality argument, both comparator branches, and quantifier order are machine-checked in Lean 4. Exact finite controls and replay commands accompany the proof.

0.07

Simultaneous Competitive and Regret Guarantees for TCP Acknowledgment

cs.LG cs.DS ·2026-10-09 ·Tsubasa Harada, Yasushi Kawase, Hanna Sumita
hot direction similarity 0.62
Abstract · 20 pages

We study simultaneous competitive and regret guarantees for TCP acknowledgment. Each acknowledgment serves all pending packets, and the objective is to minimize the total acknowledgment and waiting costs. It is well known that no deterministic online algorithm achieves a competitive ratio better than $2$. Given $k$ randomized online experts and $0<\varepsilon<1$, we construct a randomized online algorithm whose realized total cost is always at most $(2+\varepsilon)$ times the offline optimal cost $\mathrm{OPT}$ and whose expected regret against the expert with the smallest realized cost is $O(\sqrt{\mathrm{OPT}\log(k+1)}+\log(1/\varepsilon))$. The algorithm requires no advance knowledge of the number of packets or $\mathrm{OPT}$. Our algorithm controls switching costs between experts and uses the gap between the permitted competitive bound and its current cost to determine when to learn. We also prove lower bounds showing that, for $k\ge 2$, this regret bound is asymptotically optimal in $\mathrm{OPT}$, $k$, and $\varepsilon$, and that $\varepsilon>0$ is necessary for sublinear regret.

0.57

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

cs.DS ·2026-10-27 ·Junho Hwang
theory similarity 0.59
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

The $k$-server conjecture is true

cs.DS ·2026-09-14 ·Christian Coester, Elias Koutsoupias, Marek Zbysiński
theoryhighly cited similarity 0.59
Abstract

The $k$-server conjecture states that a deterministic online algorithm can achieve competitive ratio $k$ on every metric space. We prove the conjecture. Specifically, we show that the work function algorithm satisfies it. Our proof uses a natural algebraic representation of the work function as a matrix, which encodes all feasible paths to reach a configuration. In this representation, the minimum and addition operations arising in the definition of optimal costs correspond to addition and multiplication of formal expressions, and each work function value corresponds to the determinant of $k$ columns of the matrix. A request arrival updates the representation via a change of basis and row replacement. The amortized analysis is based on a potential function defined in terms of a larger matrix whose coordinates are pairs of coordinates of the original matrix representation.

0.54

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.58
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.18

A Tight $\widetilde Ω(\sqrt{m})$ Information-Theoretic Lower Bound for Randomized Online Set Cover

cs.DS ·2026-09-10 ·Ilan Doron-Arad, Joseph, Naor
theory similarity 0.58
Abstract

Online set cover is a fundamental problem in online algorithms, admitting a deterministic $O(\log m\log n)$-competitive algorithm, where $m$ is the number of sets and $n$ is the number of elements. This is essentially tight for deterministic algorithms as well as for polynomial-time randomized algorithms assuming $\mathrm{NP}\not\subseteq\mathrm{BPP}$. However, the best lower bound known for information-theoretic (computationally unlimited) randomized algorithms against an oblivious adversary is only $Ω(\log m)$, whereas the upper bound in terms of $m$ is $O(\sqrt m\log m)=\widetilde O(\sqrt m)$. We prove an $Ω(\sqrt m)$ lower bound for information-theoretic randomized unweighted online set cover, showing that even with unbounded computational power, randomization cannot achieve an $O(\log m)$-competitive ratio. Specifically, our lower bound rules out $O(\log m\cdot\log^{1/2-\varepsilon} n)$-competitive algorithms for every constant $\varepsilon>0$. Our techniques also prove an $Ω(m^{1/3})$ lower bound in the random-order model, and show that every algorithm with $poly(m)$ memory has competitive ratio $Ω(m/\log m)$, even with unlimited computation between requests.

0.25

The Competitive Ratio of Online Budgeted Allocation is Strictly Smaller than $1-1/e$

cs.DS cs.GT ·2026-10-30 ·Debmalya Panigrahi, Ian Zhang
similarity 0.58
Abstract

A well-known conjecture in online algorithms is that the (randomized) competitive ratio of online budgeted allocation is $1-1/e$. We refute this conjecture and show that every randomized online algorithm has competitive ratio at most $1 - 1/e - \varepsilon$ for a (small) absolute constant $\varepsilon > 0$.

0.11

Online and Fully-Dynamic Sorting

cs.DS ·2026-11-16 ·Yossi Azar, Sujoy Bhore, Devdan Dey, Debmalya Panigrahi, Or Vardi +1 more
theory similarity 0.57
Abstract

Online sorting asks how to place $n$ sequentially arriving elements in an array to minimize the sum of absolute differences between consecutive elements. Fully-dynamic sorting further extends the problem to allow both element insertions and deletions. Without recourse, these problems face strong lower bounds on the competitive ratio: $Ω(\sqrt{n})$ for online sorting and $Ω(n)$ for fully-dynamic sorting. In sharp contrast, we show that allowing only poly-logarithmic recourse yields at least exponential improvements in the competitive ratio for both problems:(1) Our main algorithmic result is a deterministic fully-dynamic sorting algorithm that is $O(\log^2 n)$-competitive and has $O(\log^4 n)$ amortized recourse per update. We complement this with a lower bound showing that any deterministic algorithm with any $O(\mathrm{polylog}(n))$ competitive ratio has amortized recourse at least $Ω(\sqrt{\log n})$.(2) For the insertion-only setting, we establish a family of approximation--recourse tradeoffs, including $O(\log\log n)$ competitive ratio with $O(\log\log n)$ amortized recourse. Given the lower bound in the fully-dynamic case, this result shows that the insertion-only problem yields exponentially better bounds than the fully-dynamic one.(3) Finally, we show that the stronger approximation-recourse tradeoff for the insertion-only case extends to the fully-dynamic setting when the array has $(1+\varepsilon)n$ space.

0.12