Greedy Matching in Optimal Transport with concave cost

Abstract

We consider the optimal transport problem between a set of $n$ red points and a set of $n$ blue points subject to a concave cost function such as $c(x,y)=\Vert x-y{\Vert }^p$ for $0<p<1$. Our focus is on a particularly simple matching algorithm: match the closest red and blue point, remove them both and repeat. We prove that it provides good results in any metric space $(X,d)$ when the cost function is $c(x,y)=d(x,y{)}^p$ with $0<p<1/2$. Empirically, the algorithm produces results that are remarkably close to optimal -- especially as the cost function gets more concave; this suggests that greedy matching may be a good toy model for Optimal Transport for very concave transport cost.