Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 879-891 |
Number of pages | 13 |
Journal | Random Structures and Algorithms |
Volume | 57 |
Issue number | 4 |
DOIs | |
State | Published - Dec 1 2020 |
Keywords
- discrepancy
- online algorithms
- random vectors
ASJC Scopus subject areas
- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics