Thresholds for Extreme Orientability

Thresholds for Extreme Orientability

0.00 Avg rating0 Votes
Article ID: iaor2014926
Volume: 69
Issue: 3
Start Page Number: 522
End Page Number: 539
Publication Date: Jul 2014
Journal: Algorithmica
Authors: ,
Keywords: optimization, programming: linear, heuristics
Abstract:

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, 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.

    Reviews

    Required fields are marked *. Your email address will not be published.