2019-03-16
On-Line Balancing of Random Inputs
Publication
Publication
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 ∑txtvt. 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.
Additional Metadata | |
---|---|
arXiv.org e-Print archive | |
Organisation | Networks and Optimization |
Bansal, N., & Spencer, J. (2019). On-Line Balancing of Random Inputs. arXiv.org e-Print archive. |