Thresholds for Extreme Orientability

<p>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 <em>orientations</em>of a graph, or more generally a <em>k</em>-uniform random hypergraph. A (<em>d</em>,<em>b</em>)<em>-orientation</em> is an assignment of each edge to <em>d</em> of its vertices, such that no vertex has more than <em>b</em> edges assigned to it. Conditions for the existence of such orientations have been completely documented except for the “extreme” case of (<em>k</em>−1,1)-orientations. We consider this remaining case, and establish:</p> <ul> <li> <p>The density threshold below which an orientation exists with high probability, and above which it does not exist with high probability.</p> </li> <li> <p>An algorithm for finding an orientation that runs in linear time with high probability, with explicit polynomial bounds on the failure probability.</p> </li> </ul> <p>Previously, no closed-form expression for the threshold was known. The only known algorithms for constructing (<em>k</em>−1,1)-orientations worked for <em>k</em>≤3, and were only shown to have<em>expected</em> linear running time.</p>