Up: Student Seminars for 2009
Top: Math Department Student Seminars

Design and Algorithms for Modern Kidney Exchanges


Tuomas Sandholm
Computer Science Department, Carnegie Mellon University

May 7, 2009
4:00 pm
Bailey Hall 207

Refreshments will be served in Bailey 204 at 3:45


In kidney exchanges, patients with kidney disease can obtain compatible donors by swapping their own willing but incompatible donors. The clearing problem involves finding a social welfare maximizing set of non-overlapping short cycles. We proved this NP-hard. It was one of the main obstacles to a national kidney exchange. We presented the first algorithm capable of clearing these exchanges optimally on a nationwide scale. Furthermore, clearing is an online problem where patient-donor pairs and altruistic donors appear and expire over time. Recently we developed trajectory-based online stochastic optimization algorithms (that use our optimal offline solver as a subroutine) for this. They outperform the current practice of solving each batch separately. I will share my experiences from using our algorithms in real kidney exchanges, and the generalizations we introduced. For one, we used them to launch the first never-ending altruistic donor chains. I am also involved with UNOS in designing the nationwide kidney exchange. I will discuss design considerations in modern kidney exchanges.

For additional information, send e-mail to math@union.edu or call (518) 388-6246.
Up: Student Seminars for 2009
Top: Math Department Student Seminars

Union College Math Department Home Page
Comments to: math@union.edu
Created automatically on: Tue Oct 23 05:29:31 EDT 2018