On-line balancing of random inputs

Nikhil Bansal, Joel H. Spencer

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)879-891
Number of pages13
JournalRandom Structures and Algorithms
Volume57
Issue number4
DOIs
StatePublished - Dec 1 2020

Keywords

  • discrepancy
  • online algorithms
  • random vectors

ASJC Scopus subject areas

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'On-line balancing of random inputs'. Together they form a unique fingerprint.

Cite this