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) = \|x-y\|^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.