Donor Chain Math

You have a good job now -- don't screw it up.

— Jesse Grant, father of Ulysses S. Grant. He had arranged a commission as a colonel for his son Ulysses in the Illinois Militia at the start of the Civil War. Ulysses had been having trouble getting a good job for years.

I just read an interesting article at Ars Technica on the mathematics behind setting up donor chains. The math is actually a variant of the prize-collecting traveling salesman problem, which is NP-hard.

The most common type of donor chain that I hear about is the domino donor chain (Figure 1) – there are other types of chains. The process begins when an altruistic individual steps forward to donate a kidney to a non-specific recipient.

Figure 1: Domino Donor Chain.

Figure 1: Domino Donor Chain.

Here is a recent story I saw on Youtube about a donor chain.

This entry was posted in General Mathematics. Bookmark the permalink.