2020-12-01
On-line balancing of random inputs
Publication
Publication
Random Structures & Algorithms , Volume 57 - Issue 4 p. 879- 891
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 (Formula presented.). 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 | |
---|---|
, , | |
doi.org/10.1002/rsa.20955 | |
Random Structures & Algorithms | |
Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
Bansal, N., & Spencer, J. (2020). On-line balancing of random inputs. Random Structures & Algorithms, 57(4), 879–891. doi:10.1002/rsa.20955 |