IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2602.10515.html

Quantile optimization in semidiscrete optimal transport

Author

Listed:
  • Yinchu Zhu
  • Ilya O. Ryzhov

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.

Suggested Citation

  • Yinchu Zhu & Ilya O. Ryzhov, 2026. "Quantile optimization in semidiscrete optimal transport," Papers 2602.10515, arXiv.org, revised Feb 2026.
    • Handle: RePEc:arx:papers:2602.10515
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2602.10515
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. L. R. Ford, Jr. & D. R. Fulkerson, 1956. "Solving the Transportation Problem," Management Science, INFORMS, vol. 3(1), pages 24-32, October.
    2. Rui Gao & Anton Kleywegt, 2023. "Distributionally Robust Stochastic Optimization with Wasserstein Distance," Mathematics of Operations Research, INFORMS, vol. 48(2), pages 603-655, May.
    3. Jose Blanchet & Karthyek Murthy & Fan Zhang, 2022. "Optimal Transport-Based Distributionally Robust Optimization: Structural Properties and Iterative Schemes," Mathematics of Operations Research, INFORMS, vol. 47(2), pages 1500-1529, May.
    4. Viet Anh Nguyen & Fan Zhang & Shanshan Wang & José Blanchet & Erick Delage & Yinyu Ye, 2025. "Robustifying Conditional Portfolio Decisions via Optimal Transport," Operations Research, INFORMS, vol. 73(5), pages 2801-2829, September.
    5. Kim, Jae Ho & Powell, Warren B., 2011. "An hour-ahead prediction model for heavy-tailed spot prices," Energy Economics, Elsevier, vol. 33(6), pages 1252-1266.
    6. John Gunnar Carlsson & Xiaoshan Peng & Ilya O. Ryzhov, 2024. "Demand Equilibria in Spatial Service Systems," Manufacturing & Service Operations Management, INFORMS, vol. 26(6), pages 2305-2321, November.
    7. Valentin Hartmann & Dominic Schuhmacher, 2020. "Semi-discrete optimal transport: a solution procedure for the unsquared Euclidean distance case," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 92(1), pages 133-163, August.
    8. Jiaqiao Hu & Yijie Peng & Gongbo Zhang & Qi Zhang, 2022. "A Stochastic Approximation Method for Simulation-Based Quantile Optimization," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 2889-2907, November.
    9. Paul Glasserman & Tai-Wen Liu, 1996. "Rare-Event Simulation for Multistage Production-Inventory Systems," Management Science, INFORMS, vol. 42(9), pages 1292-1307, September.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Daniel R. Jiang & Warren B. Powell, 2018. "Risk-Averse Approximate Dynamic Programming with Quantile-Based Risk Measures," Mathematics of Operations Research, INFORMS, vol. 43(2), pages 554-579, May.
    2. Ling Liang & Zusen Xu & Kim-Chuan Toh & Jia-Jie Zhu, 2025. "An Inexact Halpern Iteration with Application to Distributionally Robust Optimization," Journal of Optimization Theory and Applications, Springer, vol. 206(3), pages 1-41, September.
    3. Bo Rao & Liu Yang & Jingmin Cai, 2025. "Optimal transport-based distributionally robust optimization with polynomial uncertainty," Journal of Global Optimization, Springer, vol. 93(1), pages 215-240, September.
    4. Ilya O. Ryzhov & John Gunnar Carlsson & Yinchu Zhu, 2025. "Individual and group fairness in geographical partitioning," Papers 2511.19722, arXiv.org.
    5. M. A. Lejeune & H. N. Nguyen, 2026. "Distributionally robust fractional optimization of probability of exceedance," Journal of Global Optimization, Springer, vol. 94(1), pages 127-174, January.
    6. Tan, Mao & Jiang, Hongwei & Kuang, Yi & Li, Kang & Wang, Rui & Li, Zibin, 2025. "Electricity–carbon dual response for energy-intensive enterprise: A co-optimization approach," Renewable Energy, Elsevier, vol. 251(C).
    7. Zhu, Haohao & Wang, Xiluo & Wen, Yutong & Zhu, Jizhong & Li, Jiayi & Luo, Qingju & Liao, Chenlei, 2025. "A review of integrated energy system modeling and operation," Applied Energy, Elsevier, vol. 400(C).
    8. Kupper, Michael & Nendel, Max & Sgarabottolo, Alessandro, 2025. "Risk measures based on weak optimal transport," Center for Mathematical Economics Working Papers 734, Center for Mathematical Economics, Bielefeld University.
    9. Ama Agyeiwaa Abrokwah, 2018. "Price and Volatility Spillovers in the Electricity Reliability Council of Texas Day-Ahead Electricity Market," International Journal of Energy Economics and Policy, Econjournals, vol. 8(6), pages 322-330.
    10. Li, Zhuangzhuang & Liang, Minbo & Han, Bin & Wu, Thomas, 2025. "Flexible and low-carbon retrofit planning for wind-solar-thermal system: a distributionally robust Lipschitz dynamic programming approach," Energy, Elsevier, vol. 336(C).
    11. Hundrieser, Shayan & Mordant, Gilles & Weitkamp, Christoph A. & Munk, Axel, 2024. "Empirical optimal transport under estimated costs: Distributional limits and statistical applications," Stochastic Processes and their Applications, Elsevier, vol. 178(C).
    12. Silvana M. Pesenti & Thai Nguyen, 2026. "Outperforming a Benchmark with $\alpha$-Bregman Wasserstein divergence," Papers 2603.20580, arXiv.org.
    13. Florian F Gunsilius, 2025. "A primer on optimal transport for causal inference with observational data," Papers 2503.07811, arXiv.org, revised Mar 2025.
    14. Wang, Jinpei & Bai, Xuejie & Liu, Yankui, 2025. "Building sustainable hazardous products supply chain against ambiguous risk with accelerated Benders decomposition algorithm," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 194(C).
    15. Lersteau, Charly & Rossi, André & Sevaux, Marc, 2016. "Robust scheduling of wireless sensor networks for target tracking under uncertainty," European Journal of Operational Research, Elsevier, vol. 252(2), pages 407-417.
    16. Blessing, Jonas & Kupper, Michael & Sgarabottolo, Alessandro, 2025. "Discrete approximation of risk-based prices under volatility uncertainty," Center for Mathematical Economics Working Papers 742, Center for Mathematical Economics, Bielefeld University.
    17. Manish Singh & Tarun Kumar & Shreshtha Malik & M. K. Sharma, 2025. "A Study on the Efficiency of Genetic Algorithm in Optimizing Fuzzy Transportation Models," SN Operations Research Forum, Springer, vol. 6(4), pages 1-22, December.
    18. Shao, Zhiqi & Wang, Ze & Bell, Michael G H & Glenn Geers, D. & Gao, Junbin, 2026. "A distributionally robust chance constraint model to demand-responsive skip planning problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 206(C).
    19. Coulon, Michael & Powell, Warren B. & Sircar, Ronnie, 2013. "A model for hedging load and price risk in the Texas electricity market," Energy Economics, Elsevier, vol. 40(C), pages 976-988.
    20. Xiangyu Han & Yijun Hu & Ran Wang & Linxiao Wei, 2025. "On data-driven robust distortion risk measures for non-negative risks with partial information," Papers 2508.10682, arXiv.org.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:2602.10515. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.