Greedy Matching in Optimal Transport with concave cost

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)=\mathrm{\parallel }x-y{\mathrm{\parallel }}^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\mathrm{/}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.