On-line balancing of random inputs

Nikhil Bansal; Joel H. Spencer

doi:10.1002/rsa.20955

On-line balancing of random inputs

Nikhil Bansal (Corresponding author), Joel H. Spencer

Research output: Contribution to journal › Article › Academic › peer-review

16 Citations (Scopus)

Abstract

We consider an online vector balancing game where vectors v_t, chosen uniformly at random in {− 1, + 1}ⁿ, 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 (Formula presented.). 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.

Original language	English
Pages (from-to)	879-891
Number of pages	13
Journal	Random Structures and Algorithms
Volume	57
Issue number	4
DOIs	https://doi.org/10.1002/rsa.20955
Publication status	Published - 1 Dec 2020

Bibliographical note

Publisher Copyright:
© 2020 Wiley Periodicals LLC

Funding

This research was supported by the NWO Vici grant, 639.023.812. ERC Consolidator grant, 617951 [N.B.]. Funding information

Funders	Funder number
Seventh Framework Programme	617951
H2020 European Research Council
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	639.023.812

Keywords

discrepancy
online algorithms
random vectors

Access to Document

10.1002/rsa.20955

Cite this

@article{5794e854aea94e5daa61057c79437aca,

title = "On-line balancing of random inputs",

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

keywords = "discrepancy, online algorithms, random vectors",

author = "Nikhil Bansal and Spencer, \{Joel H.\}",

note = "Publisher Copyright: {\textcopyright} 2020 Wiley Periodicals LLC",

year = "2020",

month = dec,

day = "1",

doi = "10.1002/rsa.20955",

language = "English",

volume = "57",

pages = "879--891",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "Wiley",

number = "4",

}

TY - JOUR

T1 - On-line balancing of random inputs

AU - Bansal, Nikhil

AU - Spencer, Joel H.

PY - 2020/12/1

Y1 - 2020/12/1

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

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

KW - discrepancy

KW - online algorithms

KW - random vectors

UR - http://www.scopus.com/inward/record.url?scp=85089728432&partnerID=8YFLogxK

U2 - 10.1002/rsa.20955

DO - 10.1002/rsa.20955

M3 - Article

AN - SCOPUS:85089728432

SN - 1042-9832

VL - 57

SP - 879

EP - 891

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 4

ER -

On-line balancing of random inputs

Abstract

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this