Greedy Matching in Optimal Transport with concave cost
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916921518063616 |
|---|---|
| author | Ottolini, Andrea Steinerberger, Stefan |
| author_facet | Ottolini, Andrea Steinerberger, Stefan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_03140 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Greedy Matching in Optimal Transport with concave cost Ottolini, Andrea Steinerberger, Stefan Classical Analysis and ODEs Optimization and Control Probability 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. |
| title | Greedy Matching in Optimal Transport with concave cost |
| topic | Classical Analysis and ODEs Optimization and Control Probability |
| url | https://arxiv.org/abs/2307.03140 |