A Randomly Weighted Minimum Arborescence with a Random Cost Constraint
ALAN M. FRIEZE, Tomasz Tkocz · Mathematics of Operations Research · 2021
We study the minimum spanning arborescence problem on the complete digraph [Formula: see text], where an edge e has a weight We and a cost Ce, each of which is an independent uniform random variable Us, where [Formula: see text] and U is uniform [Formula: see text]. There is also a constraint that the spanning arborescence T must satisfy [Formula: see text]. We establish, for a range of values for [Formula: see text], the asymptotic value of the optimum weight via the consideration of a dual problem.