Quantile optimization in semidiscrete optimal transport

Yinchu Zhu and Ilya O. Ryzhov

Papers from arXiv.org

Abstract: 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.

Date: 2026-02, Revised 2026-02
References: Add references at CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2602.10515 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2602.10515

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().