A randomly weighted minimum spanning tree with a random cost constraint (Q2223477)

Summary: We study the minimum spanning tree problem on the complete graph \(K_n\) where an edge \(e\) has a weight \(W_e\) and a cost \(C_e\), each of which is an independent copy of the random variable \(U^\gamma\) where \(\gamma\leq 1\) and \(U\) is the uniform \([0,1]\) random variable. There is also a constraint that the spanning tree \(T\) must satisfy \(C(T)\leq c_0\). We establish, for a range of values for \(c_0,\gamma \), the asymptotic value of the optimum weight via the consideration of a dual problem.