A Faster Deterministic Algorithm for Kidney Exchange via Representative Set
A Faster Deterministic Algorithm for Kidney Exchange via Representative Set
Kangyi Tian, Mingyu Xiao
Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence
Main Track. Pages 2355-2363.
https://doi.org/10.24963/ijcai.2026/262
The Kidney Exchange Problem is a prominent challenge in healthcare and economics, arising in the context of organ transplantation. It has been extensively studied in artificial intelligence and optimization. In a kidney exchange, a set of donor-recipient pairs and altruistic donors are considered, with the goal of identifying a sequence of exchanges—comprising cycles or chains starting from altruistic donors—such that each donor provides a kidney to the compatible recipient in the next donor-recipient pair. These exchanges create a network of transplants aimed at maximizing the total number, t, of successful transplants. Due to constraints in medical resources, limits are often imposed on the lengths of these cycles and chains. Recently, this problem was deterministically solved in O* (14.34ᵗ) time (IJCAI 2024). In this paper, we introduce the representative set technique for the Kidney Exchange Problem, showing that the problem can be deterministically solved in O* (6.855ᵗ) time.
Keywords:
Constraint Satisfaction and Optimization: Constraint optimization problems
Game Theory and Economic Paradigms: Auctions and market-based systems
Game Theory and Economic Paradigms: Computational social choice
