Online carpooling against an oblivious adversary
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.00388
curl -X POST /api/v1/records/arxiv/2611.00388/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.00388/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'