Hostname: page-component-6587cd75c8-2cm9h Total loading time: 0 Render date: 2025-04-24T01:35:51.639Z Has data issue: false hasContentIssue false
  • English
  • Français

Extrema of a multinomial assignment process

Part of: Graph theory Special processes Combinatorial probability

Published online by Cambridge University Press:  06 June 2023

Mikhail Lifshits Open the ORCID record for Mikhail Lifshits [Opens in a new window]  and
Gilles Mordant Open the ORCID record for Gilles Mordant [Opens in a new window]
Mikhail Lifshits*
Affiliation:
St. Petersburg State University
Gilles Mordant*
Affiliation:
Universität Göttingen
*
*Postal address: St. Petersburg State University. Russia, 199034, St. Petersburg, University Emb. 7/9. Email: [email protected]
**Postal address: Institut für Mathematische Stochastik, Universität Göttingen. Göttingen, Germany. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the asymptotic behaviour of the expectation of the maxima and minima of a random assignment process generated by a large matrix with multinomial entries. A variety of results is obtained for different sparsity regimes.

Keywords

Expected maximaminimamultinomial distributionrandom assignment process

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 05C70: Factorization, matching, partitioning, covering and packing 60K30: Applications (congestion, allocation, storage, traffic, etc.)
Type
Original Article
Information
Journal of Applied Probability , Volume 61 , Issue 1 , March 2024 , pp. 198 - 213
Check for updates
Copyright
© The Author(s), 2023. Published by Cambridge University Press on behalf of Applied Probability Trust

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

Aldous, D. (1992) Asymptotics in the random assignment problem. Prob. Theory Relat. Fields 93, 507–534.CrossRefGoogle Scholar
Aldous, D. J. (2001) The $\zeta(2)$ limit in the random assignment problem. Random Structures 18, 381–418.CrossRefGoogle Scholar
Bulinski, A. V. and Shashkin, A. P. (2007) Limit Theorems for Associated Random Fields and Related Systems (Adv. Ser. Statist. Sci. Appl. Prob. 10). World Scientific, Singapore.CrossRefGoogle Scholar
Christofides, T. C. and Vaggelatou, E. (2004) A connection between supermodular ordering and positive/negative association. J. Multivar. Anal. 88, 138–151.CrossRefGoogle Scholar
Cheng, Y., Liu, Y., Tkocz, T. and Xu, A. (2023) Typical values of extremal-weight combinatorial structures with independent symmetric weights. Electron. J. Combinatorics 30, P1.12.CrossRefGoogle Scholar
Coppersmith, D. and Sorkin, G. B. (1999) Constructive bounds and exact expectations for the random assignment problem. Random Structures Algorithms 15, 113–144.3.0.CO;2-S>CrossRefGoogle Scholar
Erdös, P. and Rényi, A. (1964) On random matrices. Publ. Math. Inst. Hungar. Acad. Sci. 8, 455–461.Google Scholar
Joag-Dev, K. and Proschan, F. (1983) Negative association of random variables with applications. Ann. Statist. 11, 286–295.CrossRefGoogle Scholar
Lifshits, M. and Tadevosian, A. (2022) On the maximum of random assignment process. Statist. Prob. Lett. 187, 109530.CrossRefGoogle Scholar
Linusson, S. and Wästlund, J. (2004) A proof of Parisi’s conjecture on the random assignment problem. Prob. Theory Relat. Fields 128, 419–440.CrossRefGoogle Scholar
Mézard, M. and Parisi, G. (1987) On the solution of the random link matching problems. J. Physique 48, 1451–1459.CrossRefGoogle Scholar
Mordant, G. and Segers, J. (2021) Maxima and near-maxima of a Gaussian random assignment field. Statist. Prob. Lett. 173, 109087.CrossRefGoogle Scholar
Nair, C., Prabhakar, B. and Sharma, M. (2005) Proofs of the Parisi and Coppersmith–Sorkin random assignment conjectures. Random Structures Algorithms 27, 413–444.CrossRefGoogle Scholar
Parviainen, R. (2004) Random assignment with integer costs. Combinatorics Prob. Comput. 13, 103–113.CrossRefGoogle Scholar
Steele, J. M. (1990). Probability and statistics in the service of computer science: Illustrations using the assignment problem. Commun. Statist. Theory Meth. 19, 4315–4329.CrossRefGoogle Scholar
Steele, J. M. (1997). Probability Theory and Combinatorial Optimization (CBMS-NSF Regional Conf. Ser. Appl. Math. 69). SIAM, Philadelphia, PA.Google Scholar
Wästlund, J. (2009) An easy proof of the $\zeta (2)$ limit in the random assignment problem. Electron. Commun. Prob. 14, 261–269.Google Scholar