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. 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.
    2. 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.
    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. Itai Ashlagi & Alvin E. Roth, 2021. "Kidney Exchange: An Operations Perspective," Management Science, INFORMS, vol. 67(9), pages 5455-5478, September.
    4. 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.
    5. 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.
    6. 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.
    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. Carvalho, Margarida & Lodi, Andrea, 2023. "A theoretical and computational equilibria analysis of a multi-player kidney exchange program," European Journal of Operational Research, Elsevier, vol. 305(1), pages 373-385.
    9. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press and Oxford Review of Economic Policy Limited, vol. 33(4), pages 541-571.
    10. 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.
    11. 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.
    12. John P. Dickerson & Ariel D. Procaccia & Tuomas Sandholm, 2019. "Failure-Aware Kidney Exchange," Management Science, INFORMS, vol. 65(4), pages 1768-1791, April.
    13. 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.
    14. Naonori Kakimura & Donghao Zhu, 2021. "Dynamic Bipartite Matching Market with Arrivals and Departures," Papers 2110.10824, arXiv.org.
    15. Kratz, Jörgen, 2024. "Conflicting objectives in kidney exchange," Journal of Economic Theory, Elsevier, vol. 217(C).
    16. 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.
    17. 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.
    18. Lilla Matyasi & Péter Biró, 2024. "Testing re-optimisation strategies in international kidney exchange programmes by the ENCKEP simulator," 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. 32(4), pages 989-1011, December.
    19. Kristóf Druzsin & Péter Biró & Xenia Klimentova & Rita Fleiner, 2024. "Performance evaluation of national and international kidney exchange programmes with the ENCKEP simulator," 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. 32(4), pages 923-943, December.
    20. Santanu S. Dey & Marco Molinaro & Qianyi Wang, 2018. "Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs," Mathematics of Operations Research, INFORMS, vol. 43(1), pages 304-332, February.

    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.