Balanced allocation on dynamic hypergraphs

Catherine Greenhill, Bernard Mans, Ali Pourmiri

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

94 Downloads (Pure)

Abstract

The balls-into-bins model randomly allocates n sequential balls into n bins, as follows: each ball selects a set D of d ≥ 2 bins, independently and uniformly at random, then the ball is allocated to a least-loaded bin from D (ties broken randomly). The maximum load is the maximum number of balls in any bin. In 1999, Azar et al. showed that, provided ties are broken randomly, after n balls have been placed the maximum load, is logd log n + O(1), with high probability. We consider this popular paradigm in a dynamic environment where the bins are structured as a dynamic hypergraph. A dynamic hypergraph is a sequence of hypergraphs, say H(t), arriving over discrete times t = 1, 2,..., such that the vertex set of H(t)'s is the set of n bins, but (hyper)edges may change over time. In our model, the t-th ball chooses an edge from H(t) uniformly at random, and then chooses a set D of d ≥ 2 random bins from the selected edge. The ball is allocated to a least-loaded bin from D, with ties broken randomly. We quantify the dynamicity of the model by introducing the notion of pair visibility, which measures the number of rounds in which a pair of bins appears within a (hyper)edge. We prove that if, for some ε > 0, a dynamic hypergraph has pair visibility at most n1−ε, and some mild additional conditions hold, then with high probability the process has maximum load O(logd log n). Our proof is based on a variation of the witness tree technique, which is of independent interest. The model can also be seen as an adversarial model where an adversary decides the structure of the possible sets of d bins available to each ball.

Original languageEnglish
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Subtitle of host publicationAPPROX/RANDOM 2020, August 17–19, 2020, Virtual Conference
EditorsJarosław Byrka, Raghu Meka
Place of PublicationSaarbrücken, Germany
PublisherDagstuhl Publishing
Number of pages22
ISBN (Electronic)9783959771641
DOIs
Publication statusPublished - Aug 2020
Event23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020 - Virtual, Online, United States
Duration: 17 Aug 202019 Aug 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume176
ISSN (Print)1868-8969

Conference

Conference23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020
CountryUnited States
CityVirtual, Online
Period17/08/2019/08/20

Bibliographical note

Copyright the Author(s) 2020. Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher.

Keywords

  • Balanced allocation
  • Balls-into-bins
  • Power of two choices
  • Witness tree technique

Fingerprint Dive into the research topics of 'Balanced allocation on dynamic hypergraphs'. Together they form a unique fingerprint.

Cite this