Often, in cases where someone needs a transplant, there is a relative willing to make this sacrifice but is unable to do so because they aren’t a close enough tissue match (which would lead to the organ’s rejection by its new host’s immune system). Separately, there are some rare individuals who are simply willing to donate a kidney to an unknown recipient. So the medical community has started doing “donation chains,” where a group of donor-recipient pairs are matched so that everyone who receives a kidney has a paired donor that gives one to someone else.
That, as it turns out, has created its own problem: given a large pool of donors and recipients, how do you pull a set of optimized donor chains out? It turns out that the optimization belongs to a set of mathematical problems that are called NP-hard, making them extremely difficult to calculate as the length of the chain goes up. But now, some researchers have developed algorithms that can solve the typical challenges faced by hospitals with the processing power of a desktop computer.
via Ars Technica
Image: Karol Franks
