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.
@article{10_37236_9445,
author = {Alan Frieze and Tomasz Tkocz},
title = {A randomly weighted minimum spanning tree with a random cost constraint},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {1},
doi = {10.37236/9445},
zbl = {1456.05146},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9445/}
}
TY - JOUR
AU - Alan Frieze
AU - Tomasz Tkocz
TI - A randomly weighted minimum spanning tree with a random cost constraint
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/9445/
DO - 10.37236/9445
ID - 10_37236_9445
ER -
%0 Journal Article
%A Alan Frieze
%A Tomasz Tkocz
%T A randomly weighted minimum spanning tree with a random cost constraint
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/9445/
%R 10.37236/9445
%F 10_37236_9445
Alan Frieze; Tomasz Tkocz. A randomly weighted minimum spanning tree with a random cost constraint. The electronic journal of combinatorics, Tome 28 (2021) no. 1. doi: 10.37236/9445
