View Events By Type
Distinguished Lecturer Series
Wednesday, April 21, 2010
4:00pm - 5:00pm
Computer Science Building, Rooms 150 & 151
Faculty Host: Victor Lesser
"Design and Algorithms for Modern Kidney Exchanges"
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. The key was incremental problem formulation because the formulation that gives tight LP bounds is too large to even store. On top of the branch-and-price paradigm we developed techniques that dramatically improve runtime and memory usage. Furthermore, clearing is actually an online problem where patient-donor pairs and altruistic donors appear and expire over time. We developed trajectory-based online stochastic optimization algorithms (that use our optimal offline solver as a subroutine) for this. I will discuss design parameters and tradeoffs. Our best online algorithms outperform the current practice of solving each batch separately. I will share experiences from using our algorithms as the clearing engine of the largest two kidney exchange networks in the US. We also introduced several design enhancements to the exchanges. For one, we used our algorithms to launch the first never-ending altruistic donor chains. I am also helping UNOS design the nationwide kidney exchange, which will use our algorithms; I will discuss current design considerations.
A reception will be held at 3:40 PM in the atrium, outside the presentation room.