Load balancing and orientability thresholds for random hypergraphs

DOI10.1145/1806689.1806705MaRDI QIDQ2875136zbMATH OpenOpenAlexFDO

Authors Pu Gao, Nicholas Wormald

Publication date 13 August 2014

Published in Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

load balancingcoreshypergraph orientationorientability thresholds

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65)

Abstract: Let $h>w>0$ be two fixed integers. Let $orH$ be a random hypergraph whose hyperedges are all of cardinality $h$. To {em $w$-orient} a hyperedge, we assign exactly $w$ of its vertices positive signs with respect to the hyperedge, and the rest negative. A $(w,k)$-orientation of $orH$ consists of a $w$-orientation of all hyperedges of $orH$, such that each vertex receives at most $k$ positive signs from its incident hyperedges. When $k$ is large enough, we determine the threshold of the existence of a $(w,k)$-orientation of a random hypergraph. The $(w,k)$-orientation of hypergraphs is strongly related to a general version of the off-line load balancing problem. The graph case, when $h=2$ and $w=1$, was solved recently by Cain, Sanders and Wormald and independently by Fernholz and Ramachandran, which settled a conjecture of Karp and Saks.

Recommendations

• Orientability Thresholds for Random Hypergraphs
• The Multiple-Orientability Thresholds for Random Hypergraphs
• The multiple-orientability thresholds for random hypergraphs
• A new approach to the orientation of random hypergraphs
• Orientability of random hypergraphs and the power of multiple choices

Cited in

(14)

• The densest subgraph problem in sparse random graphs
• Load Thresholds for Cuckoo Hashing with Overlapping Blocks
• Orientability of random hypergraphs and the power of multiple choices
• Thresholds for extreme orientability
• The random graph threshold for \(k\)-orientiability and a fast algorithm for optimal multiple-choice allocation
• Load balancing for Markov chains with a specified directed graph
• The multiple-orientability thresholds for random hypergraphs
• Load balancing in hypergraphs
• Load Thresholds for Cuckoo Hashing with Overlapping Blocks
• Sandwiching a densest subgraph by consecutive cores
• Matching recovery threshold for correlated random graphs
• Orientability Thresholds for Random Hypergraphs
• A new approach to the orientation of random hypergraphs
• The Multiple-Orientability Thresholds for Random Hypergraphs

This page was built for publication: Load balancing and orientability thresholds for random hypergraphs

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