论文标题
具有独立对称权重的极大组合结构的典型值
Typical values of extremal-weight combinatorial structures with independent symmetric weights
论文作者
论文摘要
假设完整图的边缘是随机分别分配的，我们要求最小的重量跨越树，或完美匹配或哈密顿循环的重量。对于这些和其他几个常见的优化问题，当重量是对称随机变量的独立副本时，我们建立渐近紧密的边界（满足尾巴概率的轻度条件），尤其是当权重是高斯时。
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.
