IDEAS home Printed from https://ideas.repec.org/p/hrv/faseco/30830063.html
   My bibliography  Save this paper

Finding long chains in kidney exchange using the traveling salesman problem

Author

Listed:
  • Anderson, Ross
  • Ashlagi, Itai
  • Gamarnik, David
  • Roth, Alvin E.

Abstract

There are currently more than 100,000 patients on the waiting list in the United States for a kidney transplant from a deceased donor. To address this shortage, kidney exchange programs allow patients with living incompatible donors to exchange donors through cycles and chains initiated by altruistic nondirected donors. To determine which exchanges will take place, kidney exchange programs use algorithms for maximizing the number of transplants under constraints about the size of feasible exchanges. This problem is NP-hard, and algorithms previously used were unable to optimize when chains could be long. We developed two algorithms that use integer programming to solve this problem, one of which is inspired by the traveling salesman, that together can find optimal solutions in practice.

Suggested Citation

  • 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.
    • Handle: RePEc:hrv:faseco:30830063
    as

    Download full text from publisher

    File URL: http://dash.harvard.edu/bitstream/handle/1/30830063/pnas.201421853.pdf
    Download Restriction: no
    File URL: http://dash.harvard.edu/bitstream/handle/1/30830063/pnas.201421853.pdf
    Download Restriction: no
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. 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.
    2. Monica Salvioli & Roberto Lucchetti & Rosanna Torelli, 2016. "Simulating the Impact of Crossover Kidney Transplantation on the Nord Italia Transplant Program," Games, MDPI, vol. 7(4), pages 1-9, October.
    3. 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.
    4. 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.
    5. Alvin E. Roth & Robert B. Wilson, 2019. "How Market Design Emerged from Game Theory: A Mutual Interview," Journal of Economic Perspectives, American Economic Association, vol. 33(3), pages 118-143, Summer.
    6. Naonori Kakimura & Donghao Zhu, 2021. "Dynamic Bipartite Matching Market with Arrivals and Departures," Papers 2110.10824, arXiv.org.
    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.

    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:hrv:faseco:30830063. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Office for Scholarly Communication (email available below). General contact details of provider: https://edirc.repec.org/data/deharus.html .

    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.