Аннотация:
Транспортная задача Монжа–Канторовича, которую сам Монж называл «задачей о выемках и насыпях», состоит в нахождении наиболее экономного способа перевести одно заданное распределение массы в другое. В одномерном случае эта задача допускает особенно полное исследование, потому что благодаря линейной упорядоченности вещественной прямой оптимальные транспортные планы можно построить более или менее явно.
В докладе пойдет речь в основном о вогнутых ценовых функциях, которые задают на прямой «невнутренние метрики» и приводят к иерархически организованным транспортным планам. Кроме того, кое-что будет сказано о случае выпуклой ценовой функции (он гораздо проще, но все-таки не совсем тривиален), об общем случае (про который пока известно немного) и, конечно, о приложениях (среди которых есть довольно неожиданные) и вопросах, остающихся открытыми.
Список литературы
J. Delon, J. Salomon, A. Sobolevskii, “Fast transport optimization for Monge costs on the circle”, SIAM J. Appl. Math., 70:7 (2010), 2239–2258http://hal.archives-ouvertes.fr/hal-00661231
J. Delon, J. Salomon, A. Sobolevski, “Minimum-weight perfect matching for non-intrinsic distances on the line”, Записки научных семинаров ПОМИ, 390, 2011, 52–68http://hal.archives-ouvertes.fr/hal-00564173
S.K. Nechaev, A.N. Sobolevski, O.V. Valba, “On topological transition in a Random Interval Model of RNA-like chains”, 2012, arXiv: 1203.3248