Finding long chains in kidney exchange using the traveling salesman problem

Ross Anderson, Itai Ashlagi, David Gamarnik and Alvin Roth

Scholarly Articles from Harvard University Department of Economics

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.

Date: 2015
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Published in Proceedings of the National Academy of Sciences

Downloads: (external link)
http://dash.harvard.edu/bitstream/handle/1/30830063/pnas.201421853.pdf (application/pdf)
http://dash.harvard.edu/bitstream/handle/1/30830063/pnas.201421853.pdf (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:hrv:faseco:30830063

Access Statistics for this paper

More papers in Scholarly Articles from Harvard University Department of Economics Contact information at EDIRC.
Bibliographic data for series maintained by Office for Scholarly Communication ().