Oliver Chubet

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$ t…