Efficient Near-optimal Algorithms for Barter Exchange

We study polynomial-time clearing algorithms for the barter exchange problem. We put forward a family of carefully designed approximation algorithms with desirable worst-case guarantees. We further apply a series of novel heuristics to implement these algorithms. We demonstrate via kidney exchange data sets that these algorithms achieve near-optimal performances while outperforming the state-of-the-art ILP based algorithms in running time by orders of magnitude.