IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v324y2025i3p732-741.html
   My bibliography  Save this article

Maximum-expectation matching under recourse

Author

Listed:
  • Pedroso, João Pedro
  • Ikeda, Shiro

Abstract

This paper addresses the problem of maximizing the expected size of a matching in the case of unreliable vertices and/or edges. The assumption is that the solution is built in several steps. In a given step, edges with successfully matched vertices are made permanent; but upon edge or vertex failures, the remaining vertices become eligible for reassignment. This process may be repeated a given number of times, and the objective is to end with the overall maximum number of matched vertices.

Suggested Citation

  • Pedroso, João Pedro & Ikeda, Shiro, 2025. "Maximum-expectation matching under recourse," European Journal of Operational Research, Elsevier, vol. 324(3), pages 732-741.
    • Handle: RePEc:eee:ejores:v:324:y:2025:i:3:p:732-741
    DOI: 10.1016/j.ejor.2025.02.012
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221725001158
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2025.02.012?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Constantino, Miguel & Klimentova, Xenia & Viana, Ana & Rais, Abdur, 2013. "New insights on integer-programming models for the kidney exchange problem," European Journal of Operational Research, Elsevier, vol. 231(1), pages 57-68.
    2. Avrim Blum & John P. Dickerson & Nika Haghtalab & Ariel D. Procaccia & Tuomas Sandholm & Ankit Sharma, 2020. "Ignorance Is Almost Bliss: Near-Optimal Stochastic Matching with Few Queries," Operations Research, INFORMS, vol. 68(1), pages 16-34, January.
    3. Anderson, Ross & Ashlagi, Itai & Gamarnik, David & Roth, Alvin E., 2015. "Finding long chains in kidney exchange using the traveling salesman problem," Scholarly Articles 30830063, Harvard University Department of Economics.
    4. Glorie, K.M., 2012. "Estimating the probability of positive crossmatch after negative virtual crossmatch," Econometric Institute Research Papers EI 2012-25, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    5. Margarida Carvalho & Xenia Klimentova & Kristiaan Glorie & Ana Viana & Miguel Constantino, 2021. "Robust Models for the Kidney Exchange Problem," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 861-881, July.
    6. Kong, Nan & Schaefer, Andrew J., 2006. "A factor approximation algorithm for two-stage stochastic matching problems," European Journal of Operational Research, Elsevier, vol. 172(3), pages 740-746, August.
    7. Biró, Péter & van de Klundert, Joris & Manlove, David & Pettersson, William & Andersson, Tommy & Burnapp, Lisa & Chromy, Pavel & Delgado, Pablo & Dworczak, Piotr & Haase, Bernadette & Hemke, Aline & J, 2021. "Modelling and optimisation in European Kidney Exchange Programmes," European Journal of Operational Research, Elsevier, vol. 291(2), pages 447-456.
    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. Klimentova, Xenia & Biró, Péter & Viana, Ana & Costa, Virginia & Pedroso, João Pedro, 2023. "Novel integer programming models for the stable kidney exchange problem," European Journal of Operational Research, Elsevier, vol. 307(3), pages 1391-1407.
    2. Baratto, Marie & Crama, Yves & Pedroso, João Pedro & Viana, Ana, 2025. "Local stability in kidney exchange programs," European Journal of Operational Research, Elsevier, vol. 320(1), pages 20-34.
    3. Nicolau Santos & Paolo Tubertini & Ana Viana & João Pedro Pedroso, 2017. "Kidney exchange simulation and optimization," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(12), pages 1521-1532, December.
    4. Itai Ashlagi & Alvin E. Roth, 2021. "Kidney Exchange: An Operations Perspective," Management Science, INFORMS, vol. 67(9), pages 5455-5478, September.
    5. St-Arnaud, William & Carvalho, Margarida & Farnadi, Golnoosh, 2025. "Adaptation, comparison and practical implementation of fairness schemes in Kidney Exchange Programs," European Journal of Operational Research, Elsevier, vol. 325(1), pages 38-52.
    6. Mehdi Zeynivand & Mehdi Najafi & Mohammad Modarres Yazdi, 2023. "A Recourse Policy to Improve Number of Successful Transplants in Uncertain Kidney Exchange Programs," Journal of Optimization Theory and Applications, Springer, vol. 197(2), pages 476-507, May.
    7. Vicky Mak-Hau, 2017. "On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches," Journal of Combinatorial Optimization, Springer, vol. 33(1), pages 35-59, January.
    8. Glorie, K.M. & Wagelmans, A.P.M. & van de Klundert, J.J., 2012. "Iterative branch-and-price for hierarchical multi-criteria kidney exchange," Econometric Institute Research Papers EI 2012-11, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    9. Ana Viana & Xenia Klimentova & Péter Biró & Flip Klijn, 2021. "Shapley-Scarf Housing Markets: Respecting Improvement, Integer Programming, and Kidney Exchange," Working Papers 1235, Barcelona School of Economics.
    10. Escoffier, Bruno & Gourvès, Laurent & Monnot, Jérôme & Spanjaard, Olivier, 2010. "Two-stage stochastic matching and spanning tree problems: Polynomial instances and approximation," European Journal of Operational Research, Elsevier, vol. 205(1), pages 19-30, August.
    11. Naonori Kakimura & Donghao Zhu, 2021. "Dynamic Bipartite Matching Market with Arrivals and Departures," Papers 2110.10824, arXiv.org.
    12. Tom Demeulemeester & Dries Goossens & Ben Hermans & Roel Leus, 2023. "Fair integer programming under dichotomous and cardinal preferences," Papers 2306.13383, arXiv.org, revised Apr 2024.
    13. Hyunwoo Lee & Seokhyun Chung & Taesu Cheong & Sang Hwa Song, 2018. "Accounting for Fairness in a Two-Stage Stochastic Programming Model for Kidney Exchange Programs," IJERPH, MDPI, vol. 15(7), pages 1-16, July.
    14. Marcin Anholcer & Maciej Bartkowiak, 2024. "On a many-sided matching problem with mixed preferences," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 34(3), pages 1-13.
    15. Julien Combe & Victor Hiller & Olivier Tercieux & Benoît Audry & Jules Baudet & Géraldine Malaquin & François Kerbaul & Corinne Antoine & Marie-Alice Macher & Christian Jacquelinet & Olivier Bastien &, 2022. "Perspectives for future development of the kidney paired donation programme in France [Perspectives pour une évolution du programme de don croisé de reins en France]," Post-Print hal-03843902, HAL.
    16. Radu-Stefan Mincu & Péter Biró & Márton Gyetvai & Alexandru Popa & Utkarsh Verma, 2021. "IP solutions for international kidney exchange programmes," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 29(2), pages 403-423, June.
    17. Filipe Alvelos & Xenia Klimentova & Ana Viana, 2019. "Maximizing the expected number of transplants in kidney exchange programs with branch-and-price," Annals of Operations Research, Springer, vol. 272(1), pages 429-444, January.
    18. Bart Smeulders & Valentin Bartier & Yves Crama & Frits C. R. Spieksma, 2022. "Recourse in Kidney Exchange Programs," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1191-1206, March.
    19. Klimentova, Xenia & Viana, Ana & Pedroso, João Pedro & Santos, Nicolau, 2021. "Fairness models for multi-agent kidney exchange programmes," Omega, Elsevier, vol. 102(C).
    20. Demeulemeester, Tom & Goossens, Dries & Hermans, Ben & Leus, Roel, 2025. "Fair integer programming under dichotomous and cardinal preferences," European Journal of Operational Research, Elsevier, vol. 320(3), pages 465-478.

    More about this item

    Keywords

    ;
    ;
    ;

    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:eee:ejores:v:324:y:2025:i:3:p:732-741. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.