Аннотация:
Пусть $(X_{ij})$ – случайная матрица размера $n\times n$. Для перестановки $\sigma$, заданной на $\{1, \dots, n\}$, определим $S(\sigma) = \sum_{i=1}^{n} X_{i \sigma(i)}$. Изучается поведение величины $\lim_{n\to\infty} \mathbb{E}\,\max_\sigma S(\sigma)$. В докладе будет рассказано о случае как независимых $X_{ij}$, так и зависимых.
Задача имеет большое прикладное значение. Она может быть также переформулирована как выбор оптимального паросочетания в двудольном графе, на ребрах которого заданы распределения.
|
