Showing math.PRShow all
2 papers · 1 filter
math.PR2023
An Improved Drift Theorem for Balanced Allocations
Dimitrios Los, Thomas Sauerwald
In the balanced allocations framework, there are jobs (balls) to be allocated to servers (bins). The goal is to minimize the gap, the difference between the maximum and the…
math.PR2023
Mean-Biased Processes for Balanced Allocations
Dimitrios Los, Thomas Sauerwald, John Sylvester
We introduce a new class of balanced allocation processes which bias towards underloaded bins (those with load below the mean load) either by skewing the probability by which a bin…