BALANCED ALLOCATIONS FOR TREE-LIKE INPUTS

We consider the following procedure for constructing a directed tree o n n vertices: The underlying undirected tree is fixed in advance but t he edges of the tree are presented in a random order (all orders are e qually likely); each edge is oriented towards its endpoint that has th e lower indegree at the time of its insertion. The question is what is E(M(n)), the expected maximum indegree? As we shall explain, this pro blem has connections with balanced allocations and with on-line load b alancing. Previous results by Azar, Naor, and Rom imply that if the in sertion order is arbitrary, for any tree, M(n) = O(log n) and that the re are trees and insertion orders for which M(n) = Omega(log n). On th e other hand, results by Azar, Broder, Karlin, and Upfal imply that if both the underlying tree and the insertion order are random, then E(M (n)) = Theta(log log n). Here we show an intermediate result: for any tree if the insertion order is random, then E(M(n)) = O(log n/log log n) and there are trees for which E(M(n)) = Omega(log n/log log n).