On‐line balancing of random inputs
Nikhil Bansal, Joel Spencer · Random Structures and Algorithms · 2020
We consider an online vector balancing game where vectors vt, chosen uniformly at random in {− 1, + 1}n, arrive over time and a sign xt ∈ {− 1, + 1} must be picked immediately upon the arrival of vt. The goal is to minimize the L∞ norm of the signed sum . We give an online strategy for picking the signs xt that has value O(n1/2) with high probability. Up to constants, this is the best possible even when the vectors are given in advance.