Balancing sums of random vectors

Juhan Aru, Bhargav Narayanan, Alex Scott, Ramarathnam Venkatesan

Research output: Contribution to journalArticle

Abstract

We study a higher-dimensional 'balls-into-bins' problem. An infinite sequence of i.i.d. random vectors is revealed to us one vector at a time, and we are required to partition these vectors into a fixed number of bins in such a way as to keep the sums of the vectors in the different bins close together; how close can we keep these sums almost surely? This question, our primary focus in this paper, is closely related to the classical problem of partitioning a sequence of vectors into balanced subsequences, in addition to having applications to some problems in computer science.

Original languageEnglish (US)
Pages (from-to)1-17
Number of pages17
JournalDiscrete Analysis
Volume4
Issue number2018
DOIs
StatePublished - Jan 1 2018

Fingerprint

Random Vector
Balancing
Subsequence
Partitioning
Computer Science
Ball
High-dimensional
Partition

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Geometry and Topology
  • Algebra and Number Theory

Cite this

Aru, J., Narayanan, B., Scott, A., & Venkatesan, R. (2018). Balancing sums of random vectors. Discrete Analysis, 4(2018), 1-17. https://doi.org/10.19086/da.3108
Aru, Juhan ; Narayanan, Bhargav ; Scott, Alex ; Venkatesan, Ramarathnam. / Balancing sums of random vectors. In: Discrete Analysis. 2018 ; Vol. 4, No. 2018. pp. 1-17.
@article{84f97f903b19426d893fdaae843b32b0,
title = "Balancing sums of random vectors",
abstract = "We study a higher-dimensional 'balls-into-bins' problem. An infinite sequence of i.i.d. random vectors is revealed to us one vector at a time, and we are required to partition these vectors into a fixed number of bins in such a way as to keep the sums of the vectors in the different bins close together; how close can we keep these sums almost surely? This question, our primary focus in this paper, is closely related to the classical problem of partitioning a sequence of vectors into balanced subsequences, in addition to having applications to some problems in computer science.",
author = "Juhan Aru and Bhargav Narayanan and Alex Scott and Ramarathnam Venkatesan",
year = "2018",
month = "1",
day = "1",
doi = "https://doi.org/10.19086/da.3108",
language = "English (US)",
volume = "4",
pages = "1--17",
journal = "Discrete Analysis",
issn = "2397-3129",
publisher = "Alliance of Diamond Open Access Journals",
number = "2018",

}

Aru, J, Narayanan, B, Scott, A & Venkatesan, R 2018, 'Balancing sums of random vectors', Discrete Analysis, vol. 4, no. 2018, pp. 1-17. https://doi.org/10.19086/da.3108

Balancing sums of random vectors. / Aru, Juhan; Narayanan, Bhargav; Scott, Alex; Venkatesan, Ramarathnam.

In: Discrete Analysis, Vol. 4, No. 2018, 01.01.2018, p. 1-17.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Balancing sums of random vectors

AU - Aru, Juhan

AU - Narayanan, Bhargav

AU - Scott, Alex

AU - Venkatesan, Ramarathnam

PY - 2018/1/1

Y1 - 2018/1/1

N2 - We study a higher-dimensional 'balls-into-bins' problem. An infinite sequence of i.i.d. random vectors is revealed to us one vector at a time, and we are required to partition these vectors into a fixed number of bins in such a way as to keep the sums of the vectors in the different bins close together; how close can we keep these sums almost surely? This question, our primary focus in this paper, is closely related to the classical problem of partitioning a sequence of vectors into balanced subsequences, in addition to having applications to some problems in computer science.

AB - We study a higher-dimensional 'balls-into-bins' problem. An infinite sequence of i.i.d. random vectors is revealed to us one vector at a time, and we are required to partition these vectors into a fixed number of bins in such a way as to keep the sums of the vectors in the different bins close together; how close can we keep these sums almost surely? This question, our primary focus in this paper, is closely related to the classical problem of partitioning a sequence of vectors into balanced subsequences, in addition to having applications to some problems in computer science.

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

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

U2 - https://doi.org/10.19086/da.3108

DO - https://doi.org/10.19086/da.3108

M3 - Article

VL - 4

SP - 1

EP - 17

JO - Discrete Analysis

JF - Discrete Analysis

SN - 2397-3129

IS - 2018

ER -