@inproceedings{
agarwal2023fast,
title={Fast and Accurate Cost-Scaling Algorithm for the Semi-Discrete Optimal Transport},
author={Pankaj Agarwal and Sharath Raghvendra and Pouyan Shirzadian and Keegan Yao},
booktitle={NeurIPS 2023 Workshop Optimal Transport and Machine Learning},
year={2023},
url={https://openreview.net/forum?id=6Muz6c1wBc}
}
Given a continuous probability distribution $\mu$ and a discrete distribution $\nu$ in the $d$-dimensional space, the semi-discrete Optimal Transport (OT) problem asks for computing a minimum-cost plan to transport mass from $\mu$ to $\nu$.
  In this paper, given any parameter $\varepsilon>0$, we present an algorithm that computes a semi-discrete transport plan $\tilde\tau$ with cost $\textcent(\tilde\tau) \le \textcent(\tau^*)+\varepsilon$ in  $n^{O(d)}\log\frac{\mathrm{D}}{\varepsilon}$ time; here, $\tau^*$ is the optimal transport plan, $\mathrm{D}$ is the diameter of the supports of $\mu$ and $\nu$, and we assume we have access to an oracle that outputs the mass of $\mu$ inside a constant-complexity region in $O(1)$ time. Our algorithm works for several ground distances including the $L_p$-norm and the squared-Euclidean distance.
Fast and Accurate Cost-Scaling Algorithm for the Semi-Discrete Optimal Transport
Pankaj Agarwal Sharath Raghvendra Pouyan Shirzadian Keegan Yao