Abstract
The {ballsintobins 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 leastloaded 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 log_d log n + 𝒪(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 ℋ^(t), arriving over discrete times t = 1,2,…, such that the vertex set of ℋ^(t)’s is the set of n bins, but (hyper)edges may change over time. In our model, the tth ball chooses an edge from ℋ^(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 leastloaded 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 n^{1ε}, and some mild additional conditions hold, then with high probability the process has maximum load 𝒪(log_dlog 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.
BibTeX  Entry
@InProceedings{greenhill_et_al:LIPIcs:2020:12614,
author = {Catherine Greenhill and Bernard Mans and Ali Pourmiri},
title = {{Balanced Allocation on Dynamic Hypergraphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {11:111:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12614},
URN = {urn:nbn:de:0030drops126149},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.11},
annote = {Keywords: ballsintobins, balanced allocation, power of two choices, witness tree technique}
}
Keywords: 

ballsintobins, balanced allocation, power of two choices, witness tree technique 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) 
Issue Date: 

2020 
Date of publication: 

11.08.2020 