A person needing a kidney transplant may have a friend or relative who volunteers to be a living donor, but whose kidney is incompatible, forcing the person to wait for a transplant from a deceased donor. In the U.S. alone, thousands of people die each year without ever finding a suitable kidney. A new technique applies graph theory to groups of incompatible patientdonor pairs to create the largest possible number of paireddonation exchanges. These exchanges, in which a donor paired with Patient A gives a kidney to Patient B while a donor paired with Patient B gives to Patient A, will dramatically increase transplants from living donors. Since transplantation is less expensive than dialysis, this mathematical algorithm, in addition to saving lives, will also save hundreds of millions of dollars annually.
Naturally there can be more transplants if matches along longer patientdonor cycles are considered (e.g., A’s donor to B, B’s donor to C, and C’s donor to A). The problem is that the possible number of longer cycles grows so fast— hundreds of millions of A>B>C>A matches in just 5000 donorpatient pairs—that to search through all the possibilities is impossible. An ingenious use of random walks and integer programming now makes searching through all threeway matches feasible, even in a database large enough to include all incompatible patientdonor pairs.
Sommer Gentry
U.S. Naval Academy
Top image of suboptimal twoway matching (in purple) and an optimal matching (in green), courtesy of Sommer Gentry.
Matching Vital Needs
[MP3]

Listen to Sommer Gentry explain how math can increase the number of livingdonor kidney transplants and save lives.

For More Information: “Matchmaking for Kidneys,” Dana Mackenzie, SIAM News, December 2008.