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 patient-donor pairs to create the largest possible number of paired-donation 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 patient-donor 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 donor-patient pairs that to search through all the possibilities is impossible. An ingenious use of random walks and integer programming now makes searching through all three-way matches feasible, even in a database large enough to include all incompatible patient-donor pairs.

For More Information:
Matchmaking for Kidneys, Dana Mackenzie, SIAM News, December 2008.
Image of suboptimal two-way matching (in purple) and an optimal matching (in green),
courtesy of Sommer Gentry.