The Power of Filling in Balanced Allocations
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910025844260864 |
|---|---|
| author | Los, Dimitrios Sauerwald, Thomas Sylvester, John |
| author_facet | Los, Dimitrios Sauerwald, Thomas Sylvester, John |
| contents | We introduce a new class of balanced allocation processes which are primarily characterized by ``filling'' underloaded bins. A prototypical example is the Packing process: At each round we only take one bin sample, if the load is below the average load, then we place as many balls until the average load is reached; otherwise, we place only one ball. We prove that for any process in this class the gap between the maximum and average load is $\mathcal{O}(\log n)$ w.h.p. for any number of balls $m\geq 1$. For the Packing process, we also provide a matching lower bound. Additionally, we prove that the Packing process is sample-efficient in the sense that the expected number of balls allocated per sample is strictly greater than one. Finally, we also demonstrate that the upper bound of $\mathcal{O}(\log n)$ on the gap can be extended to the Memory process studied by Mitzenmacher, Prabhakar and Shah (2002). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2204_04057 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The Power of Filling in Balanced Allocations Los, Dimitrios Sauerwald, Thomas Sylvester, John Discrete Mathematics Data Structures and Algorithms Combinatorics Probability 68W20, 68W27, 68W40, 60C05 G.3; G.2.m; F.2.2 We introduce a new class of balanced allocation processes which are primarily characterized by ``filling'' underloaded bins. A prototypical example is the Packing process: At each round we only take one bin sample, if the load is below the average load, then we place as many balls until the average load is reached; otherwise, we place only one ball. We prove that for any process in this class the gap between the maximum and average load is $\mathcal{O}(\log n)$ w.h.p. for any number of balls $m\geq 1$. For the Packing process, we also provide a matching lower bound. Additionally, we prove that the Packing process is sample-efficient in the sense that the expected number of balls allocated per sample is strictly greater than one. Finally, we also demonstrate that the upper bound of $\mathcal{O}(\log n)$ on the gap can be extended to the Memory process studied by Mitzenmacher, Prabhakar and Shah (2002). |
| title | The Power of Filling in Balanced Allocations |
| topic | Discrete Mathematics Data Structures and Algorithms Combinatorics Probability 68W20, 68W27, 68W40, 60C05 G.3; G.2.m; F.2.2 |
| url | https://arxiv.org/abs/2204.04057 |