期刊
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS
卷 1, 期 4, 页码 499-517出版社
WORLD SCIENTIFIC PUBL CO PTE LTD
DOI: 10.1142/S1793830909000373
关键词
Directed graph; triangle packing; APX-completeness; approximation algorithm; exact algorithm; kidney paired donation
资金
- EPSRC [EP/E011993/1]
- OTKA [K69027]
- EPSRC [EP/E011993/1] Funding Source: UKRI
Centralized matching programs have been established in several countries to organize 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 maximize the number of transplants, but sometimes the total benefit is maximized by considering the differences between suitable kidneys. These problems correspond to computing cycle packings of maximum size or maximum weight in directed graphs. 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 an exact algorithm for the problem of finding a maximum weight exchange involving cycles of bounded length. The exact algorithm 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据