Geodesic
On a discrete max-plus transportation problem
Zapiski Nauchnykh Seminarov POMI, Boundary-value problems of mathematical physics and related problems of function theory. Part 51, Tome 536 (2024), pp. 54-78 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We provide an explicit algorithm to solve the idempotent analogue of the discrete Monge–Kantorovich optimal mass transportation problem with the usual real number field replaced by the tropical (max-plus) semiring, in which addition is defined as the maximum and product is defined as usual addition, with $-\infty$ and $0$ playing the roles of additive and multiplicative identities. Such a problem may be naturally called tropical or “max-plus” optimal transportation problem. We show that the solutions to the latter, called the optimal tropical plans, may not correspond to perfect matchings even if the data (max-plus probability measures) have all weights equal to zero, in contrast with its classical discrete optimal transportation analogue, where perfect matching optimal plans in similar situations always exist. Nevertheless, in some randomized situation the existence of perfect matching optimal tropical plans may occur rather frequently. At last, we prove that the uniqueness of solutions of the optimal tropical transportation problem is quite rare. 
@article{ZNSL_2024_536_a3,
     author = {P. Barrios and S. Mayorga and E. Stepanov},
     title = {On a discrete max-plus transportation problem},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {54--78},
     year = {2024},
     volume = {536},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2024_536_a3/}
}
TY  - JOUR
AU  - P. Barrios
AU  - S. Mayorga
AU  - E. Stepanov
TI  - On a discrete max-plus transportation problem
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2024
SP  - 54
EP  - 78
VL  - 536
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2024_536_a3/
LA  - en
ID  - ZNSL_2024_536_a3
ER  - 
%0 Journal Article
%A P. Barrios
%A S. Mayorga
%A E. Stepanov
%T On a discrete max-plus transportation problem
%J Zapiski Nauchnykh Seminarov POMI
%D 2024
%P 54-78
%V 536
%U http://geodesic.mathdoc.fr/item/ZNSL_2024_536_a3/
%G en
%F ZNSL_2024_536_a3
P. Barrios; S. Mayorga; E. Stepanov. On a discrete max-plus transportation problem. Zapiski Nauchnykh Seminarov POMI, Boundary-value problems of mathematical physics and related problems of function theory. Part 51, Tome 536 (2024), pp. 54-78. http://geodesic.mathdoc.fr/item/ZNSL_2024_536_a3/

[1] A. Basak and M. Rudelson, “Invertibility of sparse non-Hermitian matrices”, Adv. Math., 310 (2017), 426–483 | DOI | MR | Zbl

[2] B. Bollobás, Random Graphs, ed. 2, Cambridge University Press, 2010 | MR

[3] R. S. Garfinkel, K. C.Gilbert, “The bottleneck traveling salesman problem: algorithms and probabilistic analysis”, J. Assoc. Comput. Mach., 25:5 (1978), 435–448 | DOI | MR | Zbl

[4] P. C. Gilmore, R. E. Gomory, “Sequencing a one state-variable machine: A solvable case of the traveling salesman problem”, Operations Res., 12 (1964), 655–679 | DOI | MR | Zbl

[5] V. Kolokoltsov, V. P. Maslov, Idempotent analysis and its applications, Mathematics and Its Applications, Springer Netherlands, 1997 | MR

[6] C. Villani, Optimal transport: old and new, Grundlehren der Mathematischen Wissenschaften, 338, Springer-Verlag, Berlin, 2008 | MR