On-Line Balancing of Random Inputs

Abstract

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.

13 pages