arXiv preprint ·
The Online Steinitz Problem
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $\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 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+\sqrt{d\log T})$ and running time $O(dT\log 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators
A Minimum Exact Disjunctive Basis for Two-Robot Solvability Profiles
AI Discovery in Combinatorics: From Problems to Solutions and Back to Bigger Problems
A Randomized Approximation Algorithm for Doubly Free-Boundary Macdonald Processes
Selecting the 7th Smallest of 16 Elements Takes Exactly 28 Comparisons
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.