Balanced allocation on hypergraphs

DOI10.1016/J.JCSS.2023.05.004MaRDI QIDQ6133644zbMATH OpenOpenAlexFDO

Authors Catherine Greenhill, Bernard Mans, Ali Pourmiri

Publication date 21 August 2023

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

hypergraphsballs into binsbalanced allocation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Randomized algorithms (68W20) Hypergraphs (05C65)

Abstract: We consider a variation of balls-into-bins which randomly allocates $m$ balls into $n$ bins. Following Godfrey's model (SODA, 2008), we assume that each ball $t$, $1letlem$, comes with a hypergraph $mathcal{H}^{(t)}=B_1,B_2,ldots,B_{s_t}$, and each edge $Binmathcal{H}^{(t)}$ contains at least a logarithmic number of bins. Given $dge2$, our $d$-choice algorithm chooses an edge $Binmathcal{H}^{(t)}$, uniformly at random, and then chooses a set $D$ of $d$ random bins from the selected edge $B$. The ball is allocated to a least-loaded bin from $D$, with ties are broken randomly. We prove that if the hypergraphs $mathcal{H}^{(1)},ldots,mathcal{H}^{(m)}$ satisfy a emph{balancedness} condition and have low emph{pair visibility}, then after allocating $m=Theta(n)$ balls, the maximum number of balls at any bin, called the emph{maximum load}, is at most $lo{g}_{d}logn+O(1)$, with high probability. The balancedness condition enforces that bins appear almost uniformly within the hyperedges of $mathcal{H}^{(t)}$, $1letlem$, while the pair visibility condition measures how frequently a pair of bins is chosen during the allocation of balls. Moreover, we establish a lower bound for the maximum load attained by the balanced allocation for a sequence of hypergraphs in terms of pair visibility, showing the relevance of the visibility parameter to the maximum load. In Godfrey's model, each ball is forced to probe all bins in a randomly selected hyperedge and the ball is then allocated in a least-loaded bin. Godfrey showed that if each $mathcal{H}^{(t)}$, $1letlem$, is balanced and $m=O(n)$, then the maximum load is at most one, with high probability. However, we apply the power of $d$ choices paradigm, and only query the load information of $d$ random bins per ball, while achieving very slow growth in the maximum load.

Recommendations

• scientific article; zbMATH DE number 4016947
• Load balancing in hypergraphs
• Balanced graph partitioning
• A note on the balanced hypergraphs
• On balanced colorings of hypergraphs
• A class of balanced allocation problems
• Balanced allocations (extended abstract)

Cites work

• scientific article; zbMATH DE number 5764855 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• scientific article; zbMATH DE number 1857645 (Why is no real title available?)
• Balanced Allocations
• Balanced allocation on graphs
• Balls and bins: A study in negative dependence
• Balls and bins: smaller hash families and faster evaluation
• Balls into bins via local search
• Balls into bins with related random choices
• Derandomized Balanced Allocation
• Graphical balanced allocations and the (1+ )-choice process
• Hashing, load balancing and multiple choice
• How asymmetry helps load balancing
• Power of \(d\) choices with simple tabulation
• Regular graphs of large girth and arbitrary degree
• The power of thinning in balanced allocation
• The power of two choices with simple tabulation

Cited in

(5)

• A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges
• Axiomatization and Core Stability of Allocation Rules for Hypergraph Situations
• The Power of Filling in Balanced Allocations
• Derandomized Balanced Allocation
• A class of balanced allocation problems

This page was built for publication: Balanced allocation on hypergraphs

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