Quantile optimization in semidiscrete optimal transport
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914325435777024 |
|---|---|
| author | Zhu, Yinchu Ryzhov, Ilya O. |
| author_facet | Zhu, Yinchu Ryzhov, Ilya O. |
| contents | Optimal transport is the problem of designing a joint distribution for two random variables with fixed marginals. In virtually the entire literature on this topic, the objective is to minimize expected cost. This paper is the first to study a variant in which the goal is to minimize a quantile of the cost, rather than the mean. For the semidiscrete setting, where one distribution is continuous and the other is discrete, we derive a complete characterization of the optimal transport plan and develop simulation-based methods to efficiently compute it. One particularly novel aspect of our approach is the efficient computation of a tie-breaking rule that preserves marginal distributions. In the context of geographical partitioning problems, the optimal plan is shown to produce a novel geometric structure. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_10515 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Quantile optimization in semidiscrete optimal transport Zhu, Yinchu Ryzhov, Ilya O. Econometrics Methodology Optimal transport is the problem of designing a joint distribution for two random variables with fixed marginals. In virtually the entire literature on this topic, the objective is to minimize expected cost. This paper is the first to study a variant in which the goal is to minimize a quantile of the cost, rather than the mean. For the semidiscrete setting, where one distribution is continuous and the other is discrete, we derive a complete characterization of the optimal transport plan and develop simulation-based methods to efficiently compute it. One particularly novel aspect of our approach is the efficient computation of a tie-breaking rule that preserves marginal distributions. In the context of geographical partitioning problems, the optimal plan is shown to produce a novel geometric structure. |
| title | Quantile optimization in semidiscrete optimal transport |
| topic | Econometrics Methodology |
| url | https://arxiv.org/abs/2602.10515 |