Blanchet, J., Jambulapati, A., Kent, C., & Sidford, A. (2023). Towards optimal running times for optimal transport. Operations Research Letters, 52, 107054. https://doi.org/10.1016/j.orl.2023.11.007

View Publication

Abstract

We provide faster algorithms for approximating the optimal transport distance, eg earth mover's distance, between two discrete probability distributions on n elements. We present two algorithms which compute couplings between marginal distributions with an expected transportation cost that is within an additive ϵ of optimal in time O˜(n 2/ϵ); one algorithm is straightforward to parallelize and implementable in depth O˜(1/ϵ). Further, we show that additional improvements on our results must be coupled with breakthroughs in algorithmic graph theory.

Authors
Jose Blanchet, Arun Jambulapati, Carson Kent, Aaron Sidford
Publication date
2024/1/1
Journal
Operations Research Letters
Volume
52
Pages
107054
Publisher
North-Holland