Comptes Rendus
no. 15-16
Optimal Control/Numerical Analysis
Local matching indicators for concave transport costs
[Indicateurs d'appariement locaux pour le transport en coût concave]

Présenté par : Pierre-Louis Lions

Julie Delon1 ; Julien Salomon2 ; Andreĭ Sobolevskiĭ3, 4
1 LTCI CNRS, Télécom ParisTech, France
2 Université Paris-Dauphine/CEREMADE, place du Maléchal de Tassigny, 75016 Paris, France
3 A.A. Kharkevich Institute for Information Transmission Problems, Moscow, Russia
4 UMI 2615 CNRS “Laboratoire J.-V. Poncelet”, France
Comptes Rendus. Mathématique, Volume 348 (2010) no. 15-16, pp. 901-905.

Dans cette Note, nous introduisons une classe d'indicateurs permettant de calculer efficacement des plans de transport optimaux associés à des distributions arbitraires de N sources et de N puits sur la droite réelle dans le cas d'une fonction de coût concave. Ces indicateurs ont un coût de calcul faible et indépendant de N. Leur usage récursif permet, selon un certain algorithme, le calcul d'un plan de transport optimal en au plus N2 opérations.

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 R in the case where the cost function is concave. The cost of these indicators is small and independent of N. Using them recursively according to a particular algorithm allows to find an optimal transport plan in less than N2 evaluations of the cost function.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2010.07.010

Julie Delon 1 ; Julien Salomon 2 ; Andreĭ Sobolevskiĭ 3, 4

1 LTCI CNRS, Télécom ParisTech, France
2 Université Paris-Dauphine/CEREMADE, place du Maléchal de Tassigny, 75016 Paris, France
3 A.A. Kharkevich Institute for Information Transmission Problems, Moscow, Russia
4 UMI 2615 CNRS “Laboratoire J.-V. Poncelet”, France 
@article{CRMATH_2010__348_15-16_901_0,
     author = {Julie Delon and Julien Salomon and Andre\u{i} Sobolevski\u{i}},
     title = {Local matching indicators for concave transport costs},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {901--905},
     publisher = {Elsevier},
     volume = {348},
     number = {15-16},
     year = {2010},
     doi = {10.1016/j.crma.2010.07.010},
     language = {en},
}
TY  - JOUR
AU  - Julie Delon
AU  - Julien Salomon
AU  - Andreĭ Sobolevskiĭ
TI  - Local matching indicators for concave transport costs
JO  - Comptes Rendus. Mathématique
PY  - 2010
SP  - 901
EP  - 905
VL  - 348
IS  - 15-16
PB  - Elsevier
DO  - 10.1016/j.crma.2010.07.010
LA  - en
ID  - CRMATH_2010__348_15-16_901_0
ER  - 
%0 Journal Article
%A Julie Delon
%A Julien Salomon
%A Andreĭ Sobolevskiĭ
%T Local matching indicators for concave transport costs
%J Comptes Rendus. Mathématique
%D 2010
%P 901-905
%V 348
%N 15-16
%I Elsevier
%R 10.1016/j.crma.2010.07.010
%G en
%F CRMATH_2010__348_15-16_901_0
Julie Delon; Julien Salomon; Andreĭ Sobolevskiĭ. Local matching indicators for concave transport costs. Comptes Rendus. Mathématique, Volume 348 (2010) no. 15-16, pp. 901-905. doi : 10.1016/j.crma.2010.07.010. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2010.07.010/

[1] A. Aggarwal, A. Bar-Noy, S. Khuller, D. Kravets, B. Schieber, Efficient minimum cost matching using quadrangle inequality, in: Foundations of Computer Science, 1992, Proceedings of 33rd Annual Symposium, 1992, pp. 583–592.

[2] J. Delon, J. Salomon, A. Sobolevskiĭ, Local matching indicators for concave transport costs, in preparation.

[3] J. Delon; J. Salomon; A. Sobolevski Fast transport optimization for Monge costs on the circle, SIAM Journal on Applied Mathematics, Volume 70 (2010) no. 7, pp. 2239-2258

[4] R. McCann Exact solutions to the transportation problem on the line, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, Volume 455 (1999) no. 1984, pp. 1341-1380

Cité par Sources :

Commentaires - Politique