In the US alone, over 30,000 fall sick with lethal kidney disease each year, and over 77,000 await for a kidney transplant, many more than any other transplant. That demand far exceeds the supply of cadaver kidneys. It is possible for a living person to donate a kidney, e.g., to a relative or a friend, and both can live well. Unfortunately, it is unlikely that a given donor can donate to a given patient due to blood type and tissue type incompatibilities. This opens the door for kidney exchange. Consider two donor-patient pairs, A and B. Say that each of the pairs is incompatible. Yet Donor A may be able to donate to Patient B, and Donor B to Patient A. This constitutes a cycle of length two. Somewhat longer cycles are also practical. The principal investigator's prior research has proved that the exchange clearing problem is NP-complete, and developed an exchange algorithm that scales to the nationwide level.
Research under this award is scaling up and expanding the functionality of the exchange algorithms to develop (a) faster exhange algorithms (e.g., through search-tree reorganization), (b) online algorithms for deciding which cycles to select in light of changing donors and recipients, (c) algorithms that are robust to last-minute failures, and (d) using machine learning to predict the survival duration of kidney transplants and failure probabilities of last-minute tests. Some of the techniques and theory developed to address these issues also apply to other combinatorial search problems.
This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).
