REU Project

A patient who requires a kidney transplant may have a proxy donor: a person who wishes to donate a kidney to the patient, but cannot due to medical incompatibility. However, the patient may be compatible with another patient's proxy donor. Kidney exchange programs allow patients to swap proxy donors, so that each swapping patient receives a compatible transplant. The program determines which swaps occur, with the objective of maximizing the number of transplants (or a related objective representing the total health benefit to patients from transplants). At the same time, the program must account for constraints such as simultaneity of surgeries, cancellations, participation incentives and more. Mathematically, the underlying problem is what's known as a packing problem on a directed graph: finding a set of vertex-disjoint directed cycles and paths which maximize an objective function under constraints. In this project, we will designed algorithms that solve this problem for new combinations of objectives and constraints, motivated by real-world challenges faced by kidney exchange programs.