{"id":"arxiv/2611.00388","url":"https://arxiv.org/abs/2611.00388","tags":["cs.DS","math.CO","math.PR"],"score":0,"title":"Online carpooling against an oblivious adversary","domain":"cs.DS","source":"arxiv","authors":["Yuhao Lei"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-30","reactions":{}}