Typical values of extremal-weight combinatorial structures with independent symmetric weights
arXiv:2211.12348 · doi:10.37236/10237
Abstract
Suppose that the edges of a complete graph are assigned weights independently at random and we ask for the weight of the minimal-weight spanning tree, or perfect matching, or Hamiltonian cycle. For these and several other common optimisation problems, we establish asymptotically tight bounds when the weights are independent copies of a symmetric random variable (satisfying a mild condition on tail probabilities), in particular when the weights are Gaussian.
Final version. To appear in Electron. J. Combin