A randomly weighted minimum spanning tree with a random cost constraint
ALAN M. FRIEZE, Tomasz Tkocz · Society for Industrial and Applied Mathematics eBooks · 2019
We study the minimum spanning tree problem on the complete graph where an edge e has a weight We and a cost Ce, each of which is an independent uniform [0, 1] random variable. There is also a constraint that the spanning tree T must satisfy C(T) ≤ c0. We establish the asymptotic value of the optimum weight via the consideration of a dual problem. The proof is therefore constructive i.e. can be thought of as the analysis of a polynomial time algorithm. We also study the minimum spanning arborescence problem on the complete digraph where an edge e has a weight We and a cost Ce, 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) ≤ c0. 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.