EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
2204. Local stability in kidney exchange programs
Invited abstract in session TC-10: Kidney Exchange I, stream OR in Health Services (ORAHS).
Tuesday, 12:30-14:00Room: 11 (building: 116)
Authors (first author is the speaker)
| 1. | Marie Baratto
|
| Technology and Operations management, Rotterdam School of Management, Erasmus University | |
| 2. | Yves Crama
|
| HEC - Management School, University of Liège | |
| 3. | João Pedro Pedroso
|
| Campus da FEUP, INESC TEC and Faculdade de Ciencias, Universidade do Porto | |
| 4. | Ana Viana
|
| INESC TEC and ISEP -- School of Engineering, Polytechnic of Porto |
Abstract
Kidney exchange programs allow patients with end-stage renal disease to receive a kidney transplant from a living donor. The maximization of the number of transplantations within a pool of potential donors and recipients is a combinatorial optimization problem that has generated abundant literature over the past 20 years. Several authors have pointed out the relevance of the classical literature on stable matchings in this context. However, the optimization of stable kidney exchanges has not been widely investigated. We extend recent work on stable exchanges by introducing and underlining the relevance of a new concept of locally stable exchanges.
We show that locally stable exchanges in a compatibility digraph are exactly the so-called local kernels of an associated blocking digraph (whereas the stable exchanges are the kernels of the blocking digraph). We prove that it is NP-hard to determine whether a graph has a nonempty local kernel. Next, we propose several integer programming formulations for computing a locally stable exchange of maximum size. These formulations can be viewed as modeling the maximum local kernel problem in the blocking digraph. We conduct numerical experiments to assess the quality of our formulations and to compare the size of maximum locally stable exchanges with the size of maximum stable exchanges. It turns out that nonempty locally stable exchanges frequently exist in digraphs which do not have any stable exchange.
Keywords
- Health Care
- Combinatorial Optimization
- Graphs and Networks
Status: accepted
Back to the list of papers