✳flâneur — a map of the web's best reading

Clearing Kidney Exchanges via Graph Neural Network Guided Tree Search (Student Abstract) | Proceedings of the AAAI Conference on Artificial Intelligence

ojs.aaai.org · 189 words · saved by 1 readers

Kidney exchange is an organized barter market that allows patients with end-stage renal disease to trade willing donors—and thus kidneys—with other patient-donor pairs. The central clearing problem is to find an arrangement of swaps that maximizes the number of transplants. It is known to be NP-hard in almost all cases. Most existing approaches have modeled this problem as a mixed integer program (MIP), using classical branch-and-price-based tree search techniques to optimize. In this paper, we frame the clearing problem as a Maximum Weighted Independent Set (MWIS) problem, and use a Graph Neural Network guided Monte Carlo Tree Search to find a solution. Our initial results show that this approach outperforms baseline (non-optimal but scalable) algorithms. We believe that a learning-based optimization algorithm can improve upon existing approaches to the kidney exchange clearing problem. Login to access subscriber-only resources. Part of the PKP Publishing Services Network Copyright ©

Authors Zeyu Zhao Montgomery Blair High School John P. Dickerson University of Maryland DOI: https://doi.org/10.1609/aaai.v34i10.7267 Abstract Kidney exchange is an organized barter market that allows patients with end-stage renal disease to trade willing donors—and thus kidneys—with other patient-donor pairs. The central clearing problem is to find an arrangement of swaps that maximizes the number of transplants. It is known to be NP-hard in almost all cases. Most existing approaches have modeled this problem as a mixed integer program (MIP), using classical branch-and-price-based…

Explore this link on the map →

saved by

related reading