This is an archived version of CCC's website. Please visit the new ccc website for the latest information.

Relevant Links

Press Release
Research Papers
Media Contact


Kidney exchange, kidney donation, organ donation, live donation, live organ donation, kidney paired exchange, matching algorithm, clearing algorithm, exchange clearing, CMU, Carnegie Mellon University, Tuomas Sandholm, United Network for Organ Sharing, UNOS, New England Journal of Medicine


feed icon

feed icon

feed icon


Kidney Exchange Algorithm Launches Chain of 10 Transplants

An algorithm devised by Carnegie Mellon computer scientists launched a long-running chain of live kidney donations that thus far has resulted in 10 patients receiving kidney transplants, with the potential for even more. (Click on images for lager versions.)

The chain of transplants from living donors, initiated by a Michigan man who donated a kidney to a stranger, is detailed in the March 12 issue of the New England Journal of Medicine. Tuomas Sandholm, professor of computer science, is a co-author of the article.

The algorithm was devised to increase the number of kidney transplants by aiding so-called "paired donations." In these cases, a person who is willing to donate a kidney to a loved one, but is incompatible, is matched with another donor-recipient pair, and the latter pair's donor gives a kidney to the former pair. That constitutes a 2-way swap, that is, a swap between two willing but incompatible pairs. The Carnegie Mellon algorithm made three- and four-way swaps possible at scale, as well as donor chains initiated by altruistic donors. Its scalability enables the use of these ideas at the level of a nationwide kidney exchange.

The first generation of Carnegie Mellon's algorithm was developed by Sandholm, Avrim Blum, professor of computer science, and PhD student David Abraham. A more advanced algorithm, which is capable of handling the dynamics of the problem, was more recently developed by Sandholm and PhD student Pranjal Awasthi. Sandholm's research group's work on this topic is partially funded by the National Science Foundation, and by Carnegie Mellon's Center for Computational Thinking with generous support from, and collaboration with, Microsoft Research.

The United Network for Organ Sharing, which oversees U.S. organ transplants, announced that it plans to set up a national system for pairing living donors and recipients. They appointed Sandholm onto the OPTN/UNOS Kidney Paired Donation Work Group Committee.

Tuomas Sandholm []
Avrim Blum []
Pranjal Awasthi []
David Abraham []

Research support provided by:
NSF, Microsoft Research

Current Highlight | Past Highlights

Computing Research Highlight of the Week is a service of the Computing Community Consortium and the Computing Research Association designed to highlight some of the exciting and important recent research results in the computing fields. Each week a new highlight is chosen by CRA and CCC staff and volunteers from submissions from the computing community. Want your research featured? Submit it!.