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.

Authors

• Zhipeng Jia
• Pingzhong Tang Institute for Interdisciplinary Information Sciences, Tsinghua University
• Ruosong Wang
• Hanrui Zhang Simons Laufer Mathematical Sciences Institute

Keywords

• kidney exchange
• approximation algorithm
• experiments