<XML><RECORDS><RECORD><REFERENCE_TYPE>10</REFERENCE_TYPE><REFNUM>9145</REFNUM><AUTHORS><AUTHOR>Biro,P.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR><AUTHOR>Rizzi,R.</AUTHOR></AUTHORS><YEAR>2009</YEAR><TITLE>Maximum weight cycle packing in optimal kidney exchange programs</TITLE><PLACE_PUBLISHED>DCS Technical Report Series</PLACE_PUBLISHED><PUBLISHER>Dept of Computing Science, University of Glasgow</PUBLISHER><ISBN>TR-2009-298</ISBN><LABEL>Biro:2009:9145</LABEL><KEYWORDS><KEYWORD>Living kidney donation; Optimal exchange; APX-completeness; Approximation algorithm; Exact algorithm; NHS Blood and Transplant</KEYWORD></KEYWORDS<ABSTRACT>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.</ABSTRACT></RECORD></RECORDS></XML>