The Online Steinitz Problem
Abstract
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 ℝd, each of ℓ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(√T) for d≥2. Our main contribution is a general reduction that converts deterministic and randomized online vector-balancing algorithms, which assign signs to arriving vectors, into online ordering algorithms. Combined with recent vector-balancing results, this yields a randomized algorithm with prefix discrepancy O(log T+√(dlog T)) and running time O(dTlog T). The guarantee holds with high probability against an oblivious adversary. The reduction also gives bounds for sparse vectors and extends to inputs in arbitrary compact convex bodies. Finally, we prove matching lower bounds in both the deterministic and randomized cases.
Related
- A colorful Steinitz theorem with different centers
- Tusnády's problem and online two-sample thinning
- Minimax Alternating Regret for the Experts Problem and Online Convex Optimization
- Online Packet Scheduling with Deadlines and Learning
- Online tensor learning: Computational and statistical trade-offs, adaptivity and optimal regret
BibTeX
@misc{russo2026online,
title = {{The Online Steinitz Problem}},
author = {Matteo Russo and Jiaye Wei},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16715},
eprint = {2610.16715},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16715},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Online Steinitz Problem
AU - Matteo Russo
AU - Jiaye Wei
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.16715
UR - https://arxiv.org/abs/2610.16715
AB - 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 ℝ^d, each of ℓ_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(√T) for d≥2. Our main contribution is a general reduction that converts deterministic and randomized online vector-balancing algorithms, which assign signs to arriving vectors, into online ordering algorithms. Combined with recent vector-balancing results, this yields a randomized algorithm with prefix discrepancy O(log T+√(dlog T)) and running time O(dTlog T). The guarantee holds with high probability against an oblivious adversary. The reduction also gives bounds for sparse vectors and extends to inputs in arbitrary compact convex bodies. Finally, we prove matching lower bounds in both the deterministic and randomized cases.
ER -