We consider an online vector balancing game where vectors $v_t$, chosen uniformly at random in $\{ -1,+1\}^n$, arrive over time and a sign $x_t \in \{ -1,+1\}$ must be picked immediately upon the arrival of $v_t$. The goal is to minimize the $L^\infty$ norm of the signed sum $\sum_t x_t v_t$. We give an online strategy for picking the signs $x_t$ that has value $O(n^{ 1/2})$ with high probability. Up to constants, this is the best possible even when the vectors are given in advance.

Categories: cs.DS cs.DM math.PR

On-Line Balancing of Random Inputs