[Indicateurs d'appariement locaux pour le transport en coût concave]
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 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 evaluations of the cost function.
Accepté le :
Publié le :
@article{CRMATH_2010__348_15-16_901_0,
author = {Delon, Julie and Salomon, Julien and Sobolevski\u{i}, Andre\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},
url = {http://www.numdam.org/articles/10.1016/j.crma.2010.07.010/}
}
TY - JOUR AU - Delon, Julie AU - Salomon, Julien AU - Sobolevskiĭ, Andreĭ 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 UR - http://www.numdam.org/articles/10.1016/j.crma.2010.07.010/ DO - 10.1016/j.crma.2010.07.010 LA - en ID - CRMATH_2010__348_15-16_901_0 ER -
%0 Journal Article %A Delon, Julie %A Salomon, Julien %A Sobolevskiĭ, Andreĭ %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 %U http://www.numdam.org/articles/10.1016/j.crma.2010.07.010/ %R 10.1016/j.crma.2010.07.010 %G en %F CRMATH_2010__348_15-16_901_0
Delon, Julie; Salomon, Julien; Sobolevskiĭ, Andreĭ. Local matching indicators for concave transport costs. Comptes Rendus. Mathématique, Tome 348 (2010) no. 15-16, pp. 901-905. doi : 10.1016/j.crma.2010.07.010. http://www.numdam.org/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] Fast transport optimization for Monge costs on the circle, SIAM Journal on Applied Mathematics, Volume 70 (2010) no. 7, pp. 2239-2258
[4] 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 :
