On‐line balancing of random inputs. Issue 4 (25th August 2020) - Bansal, Nikhil; Spencer, Joel H.
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  ∈ {− 1,  + 1} must be picked immediately upon the arrival of v t . The goal is to minimize the L ∞ norm of the signed 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.