论文标题
高斯随机分配场的最大值和接近最大的
Maxima and near-maxima of a Gaussian random assignment field
论文作者
论文摘要
经典分配问题中成本矩阵的元素的假设独立于标准高斯分布，这激发了对对称置换组索引的特定高斯场的研究。 场的相关结构取决于两个排列之间的锤距距离。 表明，该场的最大值的期望能够以相同的方式进入无穷大，就像该场的所有变量都是独立的一样。 但是，最大值的差异显示出比独立性慢的速率收敛到零，因为方差不能小于平均分配的成本之一。 尽管如此，方差零的收敛意味着最大值具有称为超浓度的属性。 最后，显示近乎最佳分配的尺寸显示为零。
The assumption that the elements of the cost matrix in the classical assignment problem are drawn independently from a standard Gaussian distribution motivates the study of a particular Gaussian field indexed by the symmetric permutation group. The correlation structure of the field is determined by the Hamming distance between two permutations. The expectation of the maximum of the field is shown to go to infinity in the same way as if all variables of the field were independent. However, the variance of the maximum is shown to converge to zero at a rate which is slower than under independence, as the variance cannot be smaller than the one of the cost of the average assignment. Still, the convergence to zero of the variance means that the maximum possesses a property known as superconcentration. Finally, the dimension of the set of near-optimal assignments is shown to converge to zero.
