Here's a new paper just published online before print, January 5, 2015, doi: 10.1073/pnas.1421853112, PNAS January 5, 2015.
It's about the algorithms we're presently using to find optimal cycles-and-chains solutions in the kinds of sparse kidney exchange graphs we're encountering in the several programs with which we work most closely.
Finding long chains in kidney exchange using the traveling salesman problem
by Ross Anderson, Itai Ashlagi, David Gamarnik, and Alvin E. Roth
Abstract: As of May 2014 there were more than 100,000 patients on the waiting list for a kidney transplant from a deceased donor. Although the preferred treatment is a kidney transplant, every year there are fewer donors than new patients, so the wait for a transplant continues to grow. To address this shortage, kidney paired donation (KPD) programs allow patients with living but biologically incompatible donors to exchange donors through cycles or chains initiated by altruistic (nondirected) donors, thereby increasing the supply of kidneys in the system. In many KPD programs a centralized algorithm determines which exchanges will take place to maximize the total number of transplants performed. This optimization problem has proven challenging both in theory, because it is NP-hard, and in practice, because the algorithms previously used were unable to optimally search over all long chains. We give two new algorithms that use integer programming to optimally solve this problem, one of which is inspired by the techniques used to solve the traveling salesman problem. These algorithms provide the tools needed to find optimal solutions in practice.
************
Update: now published, PNAS | January 20, 2015 | vol. 112 | no. 3 | 663–668
It's about the algorithms we're presently using to find optimal cycles-and-chains solutions in the kinds of sparse kidney exchange graphs we're encountering in the several programs with which we work most closely.
Finding long chains in kidney exchange using the traveling salesman problem
by Ross Anderson, Itai Ashlagi, David Gamarnik, and Alvin E. Roth
Abstract: As of May 2014 there were more than 100,000 patients on the waiting list for a kidney transplant from a deceased donor. Although the preferred treatment is a kidney transplant, every year there are fewer donors than new patients, so the wait for a transplant continues to grow. To address this shortage, kidney paired donation (KPD) programs allow patients with living but biologically incompatible donors to exchange donors through cycles or chains initiated by altruistic (nondirected) donors, thereby increasing the supply of kidneys in the system. In many KPD programs a centralized algorithm determines which exchanges will take place to maximize the total number of transplants performed. This optimization problem has proven challenging both in theory, because it is NP-hard, and in practice, because the algorithms previously used were unable to optimally search over all long chains. We give two new algorithms that use integer programming to optimally solve this problem, one of which is inspired by the techniques used to solve the traveling salesman problem. These algorithms provide the tools needed to find optimal solutions in practice.
************
Update: now published, PNAS | January 20, 2015 | vol. 112 | no. 3 | 663–668
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.