Matching Vital Needs - Increasing the number of live-donor kidney transplants

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.