Local matching indicators for transport with concave costs

Abstract

In this note, we introduce a class of indicators that enable to compute efficiently optimal transport plans associated to arbitrary distributions of $N$ demands and $N$ supplies in $\mathbf{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.

References in corpus (1)

• Local matching indicators for transport with concave costs

Cited by in corpus (2)

• Minimum-weight perfect matching for non-intrinsic distances on the line
• Local matching indicators for transport with concave costs