Thresholds for Extreme Orientability

Details Thresholds for Extreme Orientability Thresholds for Extreme Orientability

2012-02-06

arxiv.org/abs/1202.1111v3

Computer Science

Data Structures and Algorithms

Corrected description of relationship to the work of LeLarge

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Thresholds for Extreme Orientability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Thresholds for Extreme Orientability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Thresholds for Extreme Orientability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-119348