36 citations · 118 across the 28 of their papers we have counts for
35 papers
(Almost) Perfect Discrete Iterative Load Balancing
Petra Berenbrink, Robert Elsässer, Tom Friedetzky +4
We consider discrete, iterative load balancing via matchings on arbitrary graphs. Initially each node holds a certain number of tokens, defining the load of the node, and the objec…
Time-Biased Random Walks and Robustness of Expanders
Sam Olesker-Taylor, Thomas Sauerwald, John Sylvester
Random walks on expanders play a crucial role in Markov Chain Monte Carlo algorithms, derandomization, graph theory, and distributed computing. A desirable property is that they ar…
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…
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…