The more-balls conjecture for two-thinning

Let m=Ω(n)m=\Omega(n) balls be allocated to nn bins in the two-thinning setting, and let the overseer two-thin the allocations. More-balls conjecture. The asymptotically optimal maximum load is

mn+Θ(lognloglogn).\frac{m}{n}+\Theta\left(\sqrt{\frac{\log n}{\log\log n}}\right).

This conjecture concerns the heavily loaded regime, where the number of balls is at least of order nn, and predicts the optimal deviation of the maximum load above the average load m/nm/n. The source compares it with results for power-of-kk choices in the heavily loaded balls-and-bins model; its resolution is not given here.

Sources & referencesView supporting material

Primary source

Ohad N. Feldheim and Ori Gurel-Gurevich, “The power of thinning in balanced allocation”, arXiv:1807.01132 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.