36 citations · 118 across the 28 of their papers we have counts for
18 papers · 1 filter
Rumors with Changing Credibility
Charlotte Out, Nicolás Rivera, Thomas Sauerwald +1
Randomized rumor spreading processes diffuse information on an undirected graph and have been widely studied. In this work, we present a generic framework for analyzing a broad cla…
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…