8 citations · 32 across the 9 of their papers we have counts for
4 papers · 1 filter
Balanced Allocations with the Choice of Noise
Dimitrios Los, Thomas Sauerwald
We consider the allocation of balls (jobs) into bins (servers). In the standard Two-Choice process, at each step we first sample two randomly chosen bins,…
The Power of Filling in Balanced Allocations
Dimitrios Los, Thomas Sauerwald, John Sylvester
We introduce a new class of balanced allocation processes which are primarily characterized by ``filling'' underloaded bins. A prototypical example is the Packing process: At each…
Balanced Allocations in Batches: Simplified and Generalized
Dimitrios Los, Thomas Sauerwald
We consider the allocation of balls (jobs) into bins (servers). In the Two-Choice process, for each of sequentially arriving balls, two randomly chosen bins are sampled…
Tight Bounds for Repeated Balls-into-Bins
Dimitrios Los, Thomas Sauerwald
We study the repeated balls-into-bins process introduced by Becchetti, Clementi, Natale, Pasquale and Posta (2019). This process starts with balls arbitrarily distributed acros…