Local matching indicators for transport problems with concave costs

Abstract

In this paper, we introduce a class of indicators that enable to compute efficiently optimal transport plans associated to arbitrary distributions of N demands and M supplies in R in the case where the cost function is concave. The computational cost of these indicators is small and independent of N. A hierarchical use of them enables to obtain an efficient algorithm.

Cited by in corpus (8)

• Optimal Transport with Proximal Splitting
• Differentiable Ranks and Sorting using Optimal Transport
• The Dyck bound in the concave 1-dimensional random assignment model
• Planar diagrams from optimization
• Minimum-weight perfect matching for non-intrinsic distances on the line
• Region-specific Diffeomorphic Metric Mapping
• On a solution to the Monge transport problem on the real line arising from the strictly concave case
• The p-Airy distribution