Derandomized Balanced Allocation

DOI10.1137/1.9781611975482.154MaRDI QIDQ5236343zbMATH OpenOpenAlexFDO

Authors Xue Chen

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.03375

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorics in computer science (68R05) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Abstract: In this paper, we study the maximum loads of explicit hash families in the $d$-choice schemes when allocating sequentially $n$ balls into $n$ bins. We consider the emph{Uniform-Greedy} scheme, which provides $d$ independent bins for each ball and places the ball into the bin with the least load, and its non-uniform variant --- the emph{Always-Go-Left} scheme introduced by V"ocking. We construct a hash family with $O(lognloglogn)$ random bits based on the previous work of Celis et al. and show the following results. 1. With high probability, this hash family has a maximum load of $fracloglognlogd+O(1)$ in the emph{Uniform-Greedy} scheme. 2. With high probability, it has a maximum load of $fracloglogndlogph{i}_d+O(1)$ in the emph{Always-Go-Left} scheme for a constant $ph{i}_d>1.61$. The maximum loads of our hash family match the maximum loads of a perfectly random hash function in the emph{Uniform-Greedy} and emph{Always-Go-Left} scheme separately, up to the low order term of constants. Previously, the best known hash families matching the same maximum loads of a perfectly random hash function in $d$-choice schemes were $O(logn)$-wise independent functions, which needs $Theta(lo{g}^{2}n)$ random bits.

Recommendations

• Balanced allocation through random walk
• Balanced allocations (extended abstract)
• Approximate random allocation mechanisms
• Randomized allocation processes
• Balanced allocation on hypergraphs
• A class of balanced allocation problems
• Balanced allocation on dynamic hypergraphs

Cited in

(9)

• Balls and bins: smaller hash families and faster evaluation
• Balanced allocation on hypergraphs
• scientific article; zbMATH DE number 911856 (Why is no real title available?)
• Balanced allocation on dynamic hypergraphs
• The power of two choices with simple tabulation
• Power of \(d\) choices with simple tabulation
• How asymmetry helps load balancing
• Randomized allocation processes
• Fast pseudorandomness for independence and load balancing (extended abstract)

This page was built for publication: Derandomized Balanced Allocation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236343)