The more-balls conjecture for two-thinning
The more-balls conjecture for two-thinning
Let balls be allocated to bins in the two-thinning setting, and let the overseer two-thin the allocations. More-balls conjecture. The asymptotically optimal maximum load is
This conjecture concerns the heavily loaded regime, where the number of balls is at least of order , and predicts the optimal deviation of the maximum load above the average load . The source compares it with results for power-of- 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.