On-line balancing of random inputs

DOI10.1002/RSA.20955zbMATH Open1454.91051arXiv1903.06898OpenAlexW3080328610MaRDI QIDQ3386519FDOQ3386519

Authors: N. Bansal, Joel Spencer 

Publication date: 5 January 2021

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: We consider an online vector balancing game where vectors $v_t$, chosen uniformly at random in ${-1,+1}^n$, arrive over time and a sign $x_{t}in-1,+1$ must be picked immediately upon the arrival of $v_t$. The goal is to minimize the $L^{i}nfty$ norm of the signed sum $su{m}_t{x}_t{v}_t$. 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.

Full work available at URL: https://arxiv.org/abs/1903.06898

Recommendations

• Balancing vectors in the max norm
• Balancing sums of random vectors
• Randomized algorithms for online vector load balancing
• A balancing strategy
• Vector balancing games with aging

zbMATH Keywords

online algorithmsdiscrepancyrandom vectors

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Algorithmic game theory and complexity (91A68)

Cites Work

• Twice-Ramanujan sparsifiers
• Six Standard Deviations Suffice
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• On a lemma of Littlewood and Offord
• Title not available (Why is that?)
• On Khintchine inequalities with a weight
• On a class of balancing games
• Deterministic discrepancy minimization

Cited In (8)

• Vector balancing games with aging
• Vector Balancing Games with Aging
• On the atypical solutions of the symmetric binary perceptron
• Balancing vectors in the max norm
• Discrepancy theory and related algorithms
• Algorithmic pure states for the negative spherical perceptron
• Searching for (sharp) thresholds in random structures: where are we now?
• Gaussian discrepancy: a probabilistic relaxation of vector balancing

This page was built for publication: On-line balancing of random inputs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386519)