You are here

A Sampling-free Anticipatory Algorithm for the Kidney Exchange Problem

Authors: 

Sorina Chisca, Michele Lombardi, Michela Milano, Barry O'Sullivan

Publication Type: 
Refereed Conference Meeting Proceeding
Abstract: 
Kidney exchange programs try to improve accessibility to kidney transplants by allowing incompatible patient-donor pairs to swapdonors. Running such a program requires to solve an optimization problem (the Kidney Exchange Problem, or KEP) as new pairs arrive or,unfortunately, drop-off. The KEP is a stochastic online problem, and can greatly benefit from the use of anticipatory algorithms. Unfortunately,most such algorithms suffer from scalability issues due to the reliance on scenario sampling, limiting their practical applicability. Here, we recognize that the KEP allows for a sampling-free probabilistic model of future arrivals and drop-offs, which we capture via a so-called AbstractExchange Graph (AEG). We show how an AEG-based approach can outperform sampling-based algorithms in terms of quality, while being comparable to a myopic algorithm in terms of scalability. While our cur-rent experimentation is preliminary and limited in scale, these qualities make our technique one of the few that can hope to address nation-wideprograms with thousands of enrolled pairs.
Conference Name: 
Sixteenth International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Proceedings: 
Springer Lecture Notes in Computer Science
Digital Object Identifer (DOI): 
10.1007/978-3-030-19212-9_10
Publication Date: 
03/06/2019
Volume: 
11494
Pages: 
146-162
Conference Location: 
Greece
Institution: 
National University of Ireland, Cork (UCC)
Open access repository: 
No