We study the minimum spanning arborescence problem on the complete digraph K → n , where an edge e has a weight W_(e) and a cost C_(e) , each of which is an independent uniform random variable U~(s) , where 0 U is uniform [ 0 , 1 ] . There is also a constraint that the spanning arborescence T must satisfy C ( T ) ≤ c 0 . We establish, for a range of values for c 0 , s , the asymptotic value of the optimum weight via the consideration of a dual problem.
展开▼
