Towards optimal running timesfor optimal transport

Jose H. Blanchet, Arun Jambulapati, Carson Kent, Aaron Sidford

Abstract

We provide faster algorithms for approximating the optimal transport distance, e.g. 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˜(n2/ϵ); 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.
BibTeX
@article{blanchet2024towards,
  author = {Jose H. Blanchet and Arun Jambulapati and Carson Kent and Aaron Sidford},
  title = {{Towards optimal running timesfor optimal transport}},
  journal = {Oper. Res. Lett.},
  year = {2024},
  doi = {10.1016/j.orl.2023.11.007},
}
Figure