Typical values of extremal-weight combinatorial structures with independent symmetric weights (Q2111788)

Classical optimisation problems such as minimum spanning tree, assignment problem, or shortest path have been extensively studied in the worst case as well as in the average case. In the present case, the weights drawn from symmetric distributions are considered. The edges of a complete graph are assigned weights independently at random and examined for the weight of the minimal-weight spanning tree, or perfect matching, or Hamiltonian cycle. Asymptotically tight bounds are established for this and several other common optimisation problems 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. This article is useful for researchers working on graph optimization. It is an interesting article.