An asymptotically optimal algorithm for generating bin cardinalities
<|reference_start|>An asymptotically optimal algorithm for generating bin cardinalities: In the balls-into-bins setting, $n$ balls are thrown uniformly at random into $n$ bins. The na\"{i}ve way to generate the final load vector takes $\Theta(n)$ time. However, it is well-known that this load vector has with high probability bin cardinalities of size $\Theta(\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 $\Theta(\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\"{i}ve simulation.<|reference_end|>
@article{devroye2024an,
    title={An asymptotically optimal algorithm for generating bin cardinalities},
    author={Luc Devroye, Dimitrios Los},
    journal={Mathematics and Computers in Simulation, Volume 228, February
  2025, pp. 147-155},
    year={2024},
    doi={10.1016/j.matcom.2024.08.034},
    archivePrefix={arXiv},
    eprint={2404.07011},
    primaryClass={cs.DS cs.DM}
}