Thresholds for Extreme Orientability

摘要

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 it-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: 1. The density threshold below which an orientation exists with high probability, and above which it does not exist with high probability. 2. An algorithm for finding an orientation that runs in linear time with high probability, with explicit polynomial bounds on the failure probability. Previously, no closed-form expression for the threshold was known. The only known algorithms for constructing (k-1,1)-orientations worked for k ≤ 3, and were only shown to have expected linear running time.