On‐line balancing of random inputs

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...

Full description

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 2020-12, Vol.57 (4), p.879-891
Main Authors: Bansal, Nikhil, Spencer, Joel H.
Format: Article
Language:English
Subjects:
Balancing
Computer & video games
discrepancy
online algorithms
random vectors
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1042-9832
1098-2418
DOI:10.1002/rsa.20955