Preprint
Inserted: 24 may 2024
Last Updated: 28 may 2024
Year: 2024
Abstract:
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 probabilities) have all weights equal to zero, in contrast with the classical optimal transportation analogue, where perfect matching optimal plans 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.
Keywords: optimal transportation, tropical semiring, idempotent analysis
Download: