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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

16 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Pagina's (van-tot)	879-891
Aantal pagina's	13
Tijdschrift	Random Structures and Algorithms
Volume	57
Nummer van het tijdschrift	4
DOI's	https://doi.org/10.1002/rsa.20955
Status	Gepubliceerd - 1 dec. 2020

Bibliografische nota

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

Publisher Copyright:
© 2020 Wiley Periodicals LLC

Financiering

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

Financiers	Financiernummer
Seventh Framework Programme	617951
European Research Council
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	639.023.812

Toegang tot document

10.1002/rsa.20955

Andere bestanden en links

Link naar publicatie in Scopus

Citeer dit

@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

Samenvatting

Bibliografische nota

Financiering

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit