An asymptotically optimal algorithm for generating bin cardinalities
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912018533974016 |
|---|---|
| author | Devroye, Luc Los, Dimitrios |
| author_facet | Devroye, Luc Los, Dimitrios |
| contents | In the balls-into-bins setting, $n$ balls are thrown uniformly at random into $n$ bins. The naïve way to generate the final load vector takes $Θ(n)$ time. However, it is well-known that this load vector has with high probability bin cardinalities of size $Θ(\frac{\log n}{\log \log n})$. Here, we present an algorithm in the RAM model that generates the bin cardinalities of the final load vector in the optimal $Θ(\frac{\log n}{\log \log n})$ time in expectation and with high probability.
Further, the algorithm that we present is still optimal for any $m \in [n, n \log n]$ balls and can also be used as a building block to efficiently simulate more involved load balancing algorithms. In particular, for the Two-Choice algorithm, which samples two bins in each step and allocates to the least-loaded of the two, we obtain roughly a quadratic speed-up over the naïve simulation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_07011 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An asymptotically optimal algorithm for generating bin cardinalities Devroye, Luc Los, Dimitrios Data Structures and Algorithms Discrete Mathematics 65C10, 60C05, 11K45, 68W20, 68U20, 68W27, 68W40 G.3; G.2.m; F.2.2 In the balls-into-bins setting, $n$ balls are thrown uniformly at random into $n$ bins. The naïve way to generate the final load vector takes $Θ(n)$ time. However, it is well-known that this load vector has with high probability bin cardinalities of size $Θ(\frac{\log n}{\log \log n})$. Here, we present an algorithm in the RAM model that generates the bin cardinalities of the final load vector in the optimal $Θ(\frac{\log n}{\log \log n})$ time in expectation and with high probability. Further, the algorithm that we present is still optimal for any $m \in [n, n \log n]$ balls and can also be used as a building block to efficiently simulate more involved load balancing algorithms. In particular, for the Two-Choice algorithm, which samples two bins in each step and allocates to the least-loaded of the two, we obtain roughly a quadratic speed-up over the naïve simulation. |
| title | An asymptotically optimal algorithm for generating bin cardinalities |
| topic | Data Structures and Algorithms Discrete Mathematics 65C10, 60C05, 11K45, 68W20, 68U20, 68W27, 68W40 G.3; G.2.m; F.2.2 |
| url | https://arxiv.org/abs/2404.07011 |