On a discrete max-plus transportation problem

P. Barrios ; S. Mayorga ; E. Stepanov

Zapiski Nauchnykh Seminarov POMI, Boundary-value problems of mathematical physics and related problems of function theory. Part 51, Tome 536 (2024), pp. 54-78

Résumé

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.