Paperlane

no. 7 · Tuesday 3 November 2026

Online carpooling against an oblivious adversary

Yuhao Lei

math.CO · via cs.DS · 14 pp

Abstract

In the online carpooling problem, edges on $n$ vertices arrive one at a time and must be oriented immediately, so as to keep the difference between the indegree and the outdegree of every vertex small. We give a randomized online algorithm which bounds the largest absolute difference over the first $T$ edges by $O((\log T)^{1/3})$ with high probability on every input sequence fixed in advance. This proves a conjecture of Kulkarni, Reis and Rothvoss and matches the known worst case lower bound. The algorithm keeps the law of the discrepancy vector dominated in the convex order by a Gaussian measure, and forces the endpoint with the smaller discrepancy to receive the edge whenever the two discrepancies are far apart. In the analysis we show that a vertex of discrepancy $D$ is preceded by a set of $O(D)$ vertices with total discrepancy $Ω(D^2)$.

comments
14 pages, 2 figures
fields
Combinatorics, Probability
pdf ↗ page arXiv:2611.00388 ↗