Geodesic
On the maximum of a special random assignment process
Teoriâ veroâtnostej i ee primeneniâ, Tome 67 (2022) no. 4, pp. 802-809 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider the asymptotic behavior of the expectation of the maximum for a special assignment process with constant or i.i.d. coefficients. We show how this expectation depends on the coefficients' distribution.
Keywords: asymptotic behavior, maximization, assignment process.
Mots-clés : bipartite graph 
@article{TVP_2022_67_4_a8,
     author = {M. A. Lifshits and A. A. Tadevosyan},
     title = {On the maximum of a special random assignment process},
     journal = {Teori\^a vero\^atnostej i ee primeneni\^a},
     pages = {802--809},
     year = {2022},
     volume = {67},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TVP_2022_67_4_a8/}
}
TY  - JOUR
AU  - M. A. Lifshits
AU  - A. A. Tadevosyan
TI  - On the maximum of a special random assignment process
JO  - Teoriâ veroâtnostej i ee primeneniâ
PY  - 2022
SP  - 802
EP  - 809
VL  - 67
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/TVP_2022_67_4_a8/
LA  - ru
ID  - TVP_2022_67_4_a8
ER  - 
%0 Journal Article
%A M. A. Lifshits
%A A. A. Tadevosyan
%T On the maximum of a special random assignment process
%J Teoriâ veroâtnostej i ee primeneniâ
%D 2022
%P 802-809
%V 67
%N 4
%U http://geodesic.mathdoc.fr/item/TVP_2022_67_4_a8/
%G ru
%F TVP_2022_67_4_a8
M. A. Lifshits; A. A. Tadevosyan. On the maximum of a special random assignment process. Teoriâ veroâtnostej i ee primeneniâ, Tome 67 (2022) no. 4, pp. 802-809. http://geodesic.mathdoc.fr/item/TVP_2022_67_4_a8/

[1] D. J. Aldous, “The $\zeta(2)$ limit in the random assignment problem”, Random Structures Algorithms, 18:4 (2001), 381–418 | DOI | MR | Zbl

[2] S. E. Alm, G. B. Sorkin, “Exact expectations and distributions for the random assignment problem”, Combin. Probab. Comput., 11:3 (2002), 217–248 | DOI | MR | Zbl

[3] Bo Bai, Wei Chen, Zhigang Cao, K. B. Letaief, “Max-matching diversity in OFDMA systems”, IEEE Trans. Comm., 58:4 (2010), 1161–1171 | DOI

[4] Bo Bai, Wei Chen, K. B. Letaief, Zhigang Cao, “Outage exponent: a unified performance metric for parallel fading channels”, IEEE Trans. Inform. Theory, 59:3 (2013), 1657–1677 | DOI | MR | Zbl

[5] M. W. Buck, C. S. Chan, D. P. Robbins, “On the expected value of the minimum assignment”, Random Structures Algorithms, 21:1 (2002), 33–58 | DOI | MR | Zbl

[6] Yongce Chen, Yubo Wu, Y. Thomas Hou, Wenjing Lou, “mCore: Achieving sub-millisecond scheduling for 5G MU-MIMO systems”, IEEE INFOCOM 2021 — IEEE conference on computer communications (Vancouver, BC, 2021), IEEE, 2021, 1–10 | DOI

[7] Y. Cheng, Y. Liu, T. Tkocz, A. Xu, Typical values of extremal-weight combinatorial structures with independent symmetric weights, preprint, 2021

[8] D. Coppersmith, G. B. Sorkin, “Constructive bounds and exact expectations for the random assignment problem”, Random Structures Algorithms, 15:2 (1999), 113–144 | 3.0.CO;2-S class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[9] R. V. L. Hartley, “Transmission of information”, Bell System Tech. J., 7:3 (1928), 535–563 | DOI

[10] Jintao Ke, Feng Xiao, Hai Yang, Jieping Ye, “Learning to delay in ride-sourcing systems: a multi-agent deep reinforcement learning framework”, IEEE Trans. Knowl. Data Eng., 34:5 (2020), 2280–2292 | DOI

[11] H. W. Kuhn, “The Hungarian method for the assignment problem”, Naval Res. Logist. Quart., 2:1-2 (1955), 83–97 | DOI | MR | Zbl

[12] M. Lifshits, A. Tadevosian, Gaussian assignment process, 2021, 9 pp., arXiv: 2107.04883

[13] M. A. Lifshits, A. A. Tadevosian, “On the maximum of random assignment process”, Statist. Probab. Lett., 187 (2022), 109530, 6 pp. | DOI | MR | Zbl

[14] M. Mézard, G. Parisi, “On the solution of the random link matching problems”, J. Physique, 48:9 (1987), 1451–1459 | DOI

[15] G. Mordant, J. Segers, “Maxima and near-maxima of a Gaussian random assignment field”, Statist. Probab. Lett., 173 (2021), 109087, 8 pp. | DOI | MR | Zbl

[16] C. Nair, B. Prabhakar, M. Sharma, “Proofs of the Parisi and Coppersmith–Sorkin random assignment conjectures”, Random Structures Algorithms, 27:4 (2005), 413–444 | DOI | MR | Zbl

[17] C. E. Shannon, “A mathematical theory of communication”, Bell System Tech. J., 27:4 (1948), 623–656 | DOI | MR | Zbl

[18] J. Wästlund, “An easy proof of the $\zeta(2)$ limit in the random assignment problem”, Electron. Commun. Probab., 14 (2009), 261–269 | DOI | MR | Zbl