A Scalable Constant-Factor Approximation Algorithm for $W_p$ Optimal Transport

Let $(X,d)$ be a metric space and let $\mu,\nu$ be discrete distributions supported on finite point sets $A,B \subseteq X$. For any $p \in [1,\infty]$, the $W_p$-distance between $\mu$ and $\nu$, $W_p(\mu, \nu)$, is defined as the $p$-th root of the minimum cost of transporting the mass from $\mu$ to $\nu$, where moving a unit of mass from $a \in A$ to $b \in B$ incurs a cost of $d^p(a,b)$. We give a (Las Vegas) randomized algorithm that always computes a $(4+\epsilon)$-approximate $W_p$ optimal-transport (OT) plan in $O(n^2 + (n^{3/2}\epsilon^{-1}\log^2\Delta)^{1+o(1)})$ expected time, for all $p \in [1,\infty]$, where $\epsilon > 0$ is an arbitrarily small constant and $\Delta$ is the spread of $A \cup B$. The best previous result achieved an $O(\log n)$-approximation in $O(pn^2)$ time, but only for constant $p$. Our algorithm significantly improves the approximation factor and, importantly, is the first quadratic-time method that extends to the $W_\infty$-distance. In contrast, additive approximation methods such as Sinkhorn are efficient only for constant $p$ and fail to handle $p=\infty$. Finally, we show that obtaining a relative approximation factor better than $2$ in $O(n^2)$ time would resolve the long-standing open problem of computing a perfect matching in an arbitrary bipartite graph in quadratic time.