8 citations · 32 across the 9 of their papers we have counts for
10 papers
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…
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…
Balanced Allocations in Batches: The Tower of Two Choices
Dimitrios Los, Thomas Sauerwald
In balanced allocations, the goal is to place balls into bins, so as to minimize the gap (difference of max to average load). The One-Choice process places each ball to a b…
Balanced Allocations with Heterogeneous Bins: The Power of Memory
Dimitrios Los, Thomas Sauerwald, John Sylvester
We consider the allocation of balls (jobs) into bins (servers). In the standard Two-Choice process, at each step we first sample two bins uniformly at rand…
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…
Balanced Allocations: Caching and Packing, Twinning and Thinning
Dimitrios Los, Thomas Sauerwald, John Sylvester
We consider the sequential allocation of balls (jobs) into bins (servers) by allowing each ball to choose from some bins sampled uniformly at random. The goal is to maintai…
Balanced Allocations with Incomplete Information: The Power of Two Queries
Dimitrios Los, Thomas Sauerwald
We consider the allocation of balls into bins with incomplete information. In the classical Two-Choice process a ball first queries the load of two randomly chosen bins and…