Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2602.20136 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911463191347200 |
|---|---|
| author | Mayorga, Sergio Stepanov, Eugene Barrios, Pedro |
| author_facet | Mayorga, Sergio Stepanov, Eugene Barrios, Pedro |
| contents | 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 minus infinity and zero 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 the 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_20136 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On a discrete max-plus transportation problem Mayorga, Sergio Stepanov, Eugene Barrios, Pedro Optimization and Control Combinatorics Probability 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 minus infinity and zero 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 the 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. |
| title | On a discrete max-plus transportation problem |
| topic | Optimization and Control Combinatorics Probability |
| url | https://arxiv.org/abs/2602.20136 |