A randomly weighted minimum arborescence with a random cost constraint

Abstract

We study the minimum spanning arborescence problem on the complete digraph ${\vec{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^{\alpha }$ where $\alpha \le 1$ and $U$ is uniform $[0,1]$. There is also a constraint that the spanning arborescence $T$ must satisfy $C(T)\le c_0$. We establish, for a range of values for $c_0,\alpha$, the asymptotic value of the optimum weight via the consideration of a dual problem.