{"id":"arxiv/2610.16715","url":"https://arxiv.org/abs/2610.16715","tags":["cs.DS","math.CO"],"score":0,"title":"The Online Steinitz Problem","domain":"cs.DS","source":"arxiv","authors":["Matteo Russo","Jiaye Wei"],"reviews":0,"subject":"cs.DS","summary":"Inspired by Steinitz's celebrated result (1913) and recent online vector-balancing results of Kulkarni et al. (2024) and Aden-Ali (2026), we introduce the online Steinitz problem: $T$ vectors in $\\mathbb R^d$, each of $\\ell_2$-norm at most $1$ and with total sum zero, arrive one at a time and must be assigned immediately and irrevocably to unused positions of an array. The goal is to keep every prefix sum of the resulting order small. We first obtain deterministic prefix-discrepancy bounds of $O(\\log T)$ for $d=1$ and $O(\\sqrt T)$ for $d\\ge2$. Our main contribution is a general reduction…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-12","reactions":{}}