Multiple-choice load balancing has been a topic of intense study since the seminal paper of Azar, Broder, Karlin, and Upfal. Questions in this area can be phrased in terms of orientations of a graph, or more generally a k-uniform random hypergraph. A (d,b)-orientation is an assignment of each edge to d of its vertices, such that no vertex has more than b edges assigned to it. Conditions for the existence of such orientations have been completely documented except for the "extreme" case of (k-1,1)-orientations. We consider this remaining case, and establish: - The density threshold below which an orientation exists with high probability, and above which it does not exist with high probability. - An algorithm for finding an orientation that runs in linear time with high probability, with explicit polynomial bounds on the failure probability. Previously, the only known algorithms for constructing (k-1,1)-orientations worked for k<=3, and were only shown to have expected linear running time.
@cite_18: A k-uniform hypergraph H = (V, E) is called l-orientable, if there is an assignment of each edge e e E to one of its vertices v e e such that no vertex is assigned more than l edges. Let Hn,m,k be a hypergraph, drawn uniformly at random from the set of all k-uniform hypergraphs with n vertices and m edges. In this paper we establish the threshold for the l-orientability of Hn,m,k for all k ≥ 3 and l ≥ 1, i.e., we determine a critical quantity c*k,l such that with probability 1 − o(1) the graph Hn,cn,k has an l-orientation if c c*k,l. Our result has various applications including sharp load thresholds for cuckoo hashing, load balancing with guaranteed maximum load, and massive parallel access to hard disk arrays.
@cite_14: Let h>w>0 be two fixed integers. Let H be a random hypergraph whose hyperedges are all of cardinality h. To 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 H consists of a w-orientation of all hyperedges of H, 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, thereby settling a conjecture made by Karp and Saks. Motivated by a problem of cuckoo hashing, the special hypergraph case with w=k=1, was solved in three separate preprints dating from October 2009, by Frieze and Melsted, by Fountoulakis and Panagiotou, and by Dietzfelbinger, Goerdt, Mitzenmacher, Montanari, Pagh and Rink.
@cite_4: 
@cite_7: A h-uniform hypergraph H=(V,E) is called (l,k)-orientable if there exists an assignment of each hyperedge e to exactly l of its vertices such that no vertex is assigned more than k hyperedges. Let H_ n,m,h be a hypergraph, drawn uniformly at random from the set of all h-uniform hypergraphs with n vertices and m edges. In this paper, we determine the threshold of the existence of a (l,k)-orientation of H_ n,m,h for k>=1 and h>l>=1, extending recent results motivated by applications such as cuckoo hashing or load balancing with guaranteed maximum load. Our proof combines the local weak convergence of sparse graphs and a careful analysis of a Gibbs measure on spanning subgraphs with degree constraints. It allows us to deal with a much broader class than the uniform hypergraphs.
@cite_9: A hypergraph H = (V,E) is called s-orientable, if there is an assignment of each edge e ∈ E to one of its vertices v ∈ e such that no vertex is assigned more than s edges. Let Hn,m,k be a hypergraph, drawn uniformly at random from the set of all k-uniform hypergraphs with n vertices and m edges. In this paper we establish the threshold for the 1-orientability of Hn,m,k for all k ≥ 3, i.e., we determine a critical quantity ck* such that with probability 1 - o(1) the graph Hn,cn,k has a 1-orientation if c ck*. We present two applications of this result that involve the paradigm of multiple choices. First, we show how it implies sharp load thresholds for cuckoo hash tables, where each element chooses k out of n locations. Particularly, for each k ≥ 3 we prove that with probability 1 - o(1) the maximum number of elements that can be hashed is (1 - o(1))ck*n, and more items prevent the successful allocation. Second, we study random graph processes, where in each step we have the choice among any edge connecting k random vertices. Here we show the existence of a phase transition for avoiding a giant connected component, and quantify precisely the dependence on k.
@cite_5: We investigate a linear time greedy algorithm for the following load balancing problem: Assign m balls to n bins such that the maximum occupancy is minimized. Each ball can be placed into one of two randomly choosen bins. This problem is closely related to the problem of orienting the edges of an undirected graph to obtain a directed graph with minimum in-degree. Using differential equation methods, we derive thresholds for the solution quality achieved by our algorithm. Since these thresholds coincide with lower bounds for the achievable solution quality, this proves the optimality of our algorithm (as n → ∞, in a probabilistic sense) and establishes the thresholds for k-orientability of random graphs. This proves an assertion of Karp and Saks.
@cite_16: We settle the question of tight thresholds for offline cuckoo hashing. The problem can be stated as follows: we have n keys to be hashed into m buckets each capable of holding a single key. Each key has k ≥ 3 (distinct) associated buckets chosen uniformly at random and independently of the choices of other keys. A hash table can be constructed successfully if each key can be placed into one of its buckets. We seek thresholds ck such that, as n goes to infinity, if n m ≤ c for some c ck a hash table cannot be constructed successfully with high probability. Here we are considering the offline version of the problem, where all keys and hash values are given, so the problem is equivalent to previous models of multiple-choice hashing. We find the thresholds for all values of k > 2 by showing that they are in fact the same as the previously known thresholds for the random k-XORSAT problem.We then extend these results to the setting where keys can have differing number of choices, and make a conjecture (based on experimental observations) that extends our result to cuckoo hash tables storing multiple keys in a bucket.
@cite_10: We prove that, for k ≥ 2, the k-orientability threshold for the random graph Gn, p coincides with the threshold at which the (k + 1)-core has average degree 2k. The proof involves the analysis of a heuristic algorithm that attempts to find a k-orientation of the random graph. The k-orientation threshold has several applications including offline balanced allocation with a limit of k on maximum bin-size, perfect hashing with a limit of k on maximum chain-length, and concurrent access to parallel memories through redundancy,
@cite_12: 
@cite_17: We study the the following question in Random Graphs. We are given two disjoint sets L,R with |L| = n and |R| = m. We construct a random graph G by allowing each x∈L to choose d random neighbours in R. The question discussed is as to the size μ(G) of the largest matching in G. When considered in the context of Cuckoo Hashing, one key question is as to when is μ(G) = n whp? We answer this question exactly when d is at least three. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 © 2012 Wiley Periodicals, Inc.
In the off-line setting, the threshold for @math -orientations with @math can be shown (see, e.g. @cite_12 ) to coincide with the appearance of a giant component in the random graph, which is known to happen at @math with high probability @cite_4 . Several groups of researchers @cite_16 @cite_9 @cite_17 independently established the thresholds for @math -orientations for every @math . Generalizing in another direction, Fernholz and Ramachandran @cite_10 and Cain, Sanders, and Wormald @cite_5 showed thresholds for @math -orientations for @math , and gave expected linear time algorithms for computing an orientation. This result was later extended to @math by @cite_18 . Gao and Wormald @cite_14 established thresholds for @math -orientations, given that @math is a sufficiently large constant (depending on @math and @math ). Independently of our work, Lelarge @cite_7 recently developed new technical machinery for this problem, which handles all combinations of the parameters @math , @math , and @math that satisfy @math .