An Improved Drift Theorem for Balanced Allocations

In the balanced allocations framework, there are \(m\) jobs (balls) to be allocated to \(n\) servers (bins). The goal is to minimize the gap, the difference between the maximum and the average load. In 2015, Peres, Talwar and Wieder used the hyperbolic cosine potential function to analyze the challe...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on algorithms 2024-10, Vol.20 (4), p.1-39, Article 35
Main Authors: Los, Dimitrios, Sauerwald, Thomas
Format: Article
Language:English
Subjects:
Computer Science
Data Structures and Algorithms
Discrete Mathematics
Distributed algorithms
Mathematics
Mathematics of computing
Parallel algorithms
Probabilistic algorithms
Probability
Randomness, geometry and discrete structures
Theory of computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!