Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 9 min ago
PreprintarXiv licencearXiv

Online carpooling against an oblivious adversary

  • Yuhao Lei
Open at sourcePDFDOICite

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 Ω(D2).

Related

  1. Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
    Mengxiao Zhang
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  2. Spectral Koopman-Hopf Formula for Reachability with Adversary
    Sarang Sutavani, Umesh Vaidya
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  3. Quantum-State Oblivious Transfer over Quantum Erasure Channels
    Remi A. Chou
    arXivPreprintarXiv licenceFull textGeneral mathematicsQuantum physics & quantum informationarXiv
  4. SparseStack Is an Optimal Oblivious Subspace Embedding
    Diar Heidary
    arXivPreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv
  5. Oblivious Learning and Collusive Pricing
    Yuhang Wu, Assaf Zeevi
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{lei2026online,
  title = {{Online carpooling against an oblivious adversary}},
  author = {Yuhao Lei},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.00388},
  eprint = {2611.00388},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.00388},
}
RIS
TY  - UNPB
TI  - Online carpooling against an oblivious adversary
AU  - Yuhao Lei
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.00388
UR  - https://arxiv.org/abs/2611.00388
AB  - 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).
ER  -