A randomly weighted minimum arborescence with a random cost constraint
share
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 [0,1] random variable. There is also a constraint that the spanning arborescence T must satisfy C(T)≤ c_0. We establish the asymptotic value of the optimum weight via the consideration of a dual problem. The proof is via the analysis of a polynomial time algorithm.
READ FULL TEXT