Computing at Glasgow University
Paper ID: 9145
DCS Tech Report Number: TR-2009-298

Maximum weight cycle packing in optimal kidney exchange programs
Biro,P. Manlove,D.F. Rizzi,R.

Publication Type: Tech Report (internal)
Appeared in: DCS Technical Report Series
Page Numbers :
Publisher: Dept of Computing Science, University of Glasgow
Year: 2009

Centralised matching programs have been established in several countries to organise kidney exchanges between incompatible patient-donor pairs. At the heart of these programs are algorithms to solve kidney exchange problems, which can be modelled as cycle packing problems in a directed graph, involving cycles of length 2, 3, or even longer. Usually the goal is to maximise the number of transplants, but sometimes the total benefit is maximised by considering the differences between suitable kidneys. These problems correspond to computing cycle packings of maximum size or maximum weight. Here we prove the APX-completeness of the problem of finding a maximum size exchange involving only 2-cycles and 3-cycles. We also present an approximation algorithm and two exact algorithms for the problem of finding a maximum weight exchange involving cycles of bounded length. One of the exact algorithms has been used to provide optimal solutions to real kidney exchange problems arising from the National Matching Scheme for Paired Donation run by NHS Blood and Transplant, and we describe practical experience based on this collaboration.

Keywords: Living kidney donation; Optimal exchange; APX-completeness; Approximation algorithm; Exact algorithm; NHS Blood and Transplant

PDF Bibtex entry Endnote XML