## 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 log_{d} 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 *n*^{1−ε}, and some mild additional conditions hold, then with high probability the process has maximum load *O*(log_{d} 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 language | English |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques |

Subtitle of host publication | APPROX/RANDOM 2020, August 17–19, 2020, Virtual Conference |

Editors | Jarosław Byrka, Raghu Meka |

Place of Publication | Saarbrücken, Germany |

Publisher | Dagstuhl Publishing |

Number of pages | 22 |

ISBN (Electronic) | 9783959771641 |

DOIs | |

Publication status | Published - Aug 2020 |

Event | 23rd 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 2020 → 19 Aug 2020 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 176 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020 |
---|---|

Country | United States |

City | Virtual, Online |

Period | 17/08/20 → 19/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