Greedy Matching in Optimal Transport with concave cost

Authors Andrea Ottolini, Stefan Steinerberger

Publication date 6 July 2023

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.

This page was built for publication: Greedy Matching in Optimal Transport with concave cost

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6442870)