A randomly weighted minimum spanning tree with a random cost constraint (Q2223477)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A randomly weighted minimum spanning tree with a random cost constraint |
scientific article |
Statements
A randomly weighted minimum spanning tree with a random cost constraint (English)
0 references
29 January 2021
0 references
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.
0 references
symmetric logarithmic Sobolev inequality
0 references
asymptotic value of the optimum weight
0 references
0 references
0 references
0 references