file.pdf (353.25 kB)
0/0

Thresholds for Extreme Orientability

Download (353.25 kB)
journal contribution
posted on 01.02.2012 by Po-Shen Loh, Rasmus Pagh

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 orientationsof 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, 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 haveexpected linear running time.

History

Publisher Statement

The final publication is available at Springer via http://dx.doi.org/10.1007/s00453-013-9749-4

Date

01/02/2012

Exports

Exports