Maxima and near-maxima of a Gaussian random assignment field. (English) Zbl 1482.60069
Summary: 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.
MSC:
| 60G70 | Extreme value theory; extremal stochastic processes |
| 60G15 | Gaussian processes |
| 60G60 | Random fields |
Keywords:
extremal field; Gaussian random field; near maximal set; random assignment; superconcentrationReferences:
| [1] | Aldous, D., The \(\zeta (2)\) limit in the random assignment problem, Random Struct. Algorithms, 18, 4, 381-418 (2001) · Zbl 0993.60018 |
| [2] | Aldous, D.; Steele, M. J., The objective method: probabilistic combinatorial optimization and local weak convergence, (Probability on Discrete Structures (2004), Springer), 1-72 · Zbl 1037.60008 |
| [3] | Chatterjee, S., Superconcentration and related topics, Springer Monographs in Mathematics (2014), Springer: Springer Cham · Zbl 1288.60001 |
| [4] | Chatterjee, S., A general method for lower bounds on fluctuations of random variables, Ann. Probab., 47, 4, 2140-2171 (2019) · Zbl 1451.60026 |
| [5] | Ding, J.; Eldan, R.; Zhai, A., On multiple peaks and moderate deviations for the supremum of a Gaussian field, Ann. Probab., 43, 6, 3468-3493 (2015) · Zbl 1344.60039 |
| [6] | Krokhmal, P. A.; Grundel, D. A.; Pardalos, P. M., Asymptotic behavior of the expected optimal value of the multidimensional assignment problem, Math. Program., 109, 2-3, Ser. B, 525-551 (2007) · Zbl 1147.90033 |
| [7] | Krokhmal, P. A.; Pardalos, P. M., Random assignment problems, European J. Oper. Res., 194, 1, 1-17 (2009) · Zbl 1179.90212 |
| [8] | Leadbetter, M. R.; Lindgren, G.; Rootzén, H., Extremes and related properties of random sequences and processes (1983), Springer-Verlag: Springer-Verlag New York · Zbl 0518.60021 |
| [9] | Mézard, M.; Parisi, G., On the solution of the random link matching problems, J. Physique, 48, 9, 1451-1459 (1987) |
| [10] | Mittal, Y.; Ylvisaker, D., Limit distributions for the maxima of stationary Gaussian processes, Stochastic Process. Appl., 3, 1, 1-18 (1975) · Zbl 0296.60021 |
| [11] | Panaretos, V. M.; Zemel, Y., Statistical aspects of wasserstein distances, Ann. Rev. Stat. Appl., 6, 405-431 (2019) |
| [12] | Pardalos, P. M.; Ramakrishnan, K., On the expected optimal value of random assignment problems: Experimental results and open questions, Comput. Optim. Appl., 2, 3, 261-271 (1993) · Zbl 0804.90108 |
| [13] | Resnick, S. I., Extreme values, regular variation, and point processes, Applied Probability. A Series of the Applied Probability Trust, xii+320 (1987), Springer-Verlag: Springer-Verlag New York · Zbl 1136.60004 |
| [14] | Talagrand, M., Concentration of measure and isoperimetric inequalities in product spaces, Publ. Math. l’Inst. Hautes Etudes Sci., 81, 1, 73-205 (1995) · Zbl 0864.60013 |
| [15] | Tanguy, K., Some superconcentration inequalities for extrema of stationary Gaussian processes, Statist. Probab. Lett., 106, 239-246 (2015) · Zbl 1397.60071 |
| [16] | Wästlund, J., The variance and higher moments in the random assignment problem (2005), Linköping University Electronic Press |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
