Randomized Algorithms for Parameterized Kidney Exchange Problem
Kidney exchange programs have been established in several countries to organize kidney exchanges between incompatible patient-donor pairs.The core of these programs are algorithms to solve kidney exchange problem, which can be modeled as finding a maximum weight packing of vertex-disjoint cycles with length at most some small constant L (typically 2 ≤ L ≤ 5) in a directed graph.In generally, the objective function is maximizing the number of possible kidney transplants.In this paper, we study the random methods for the kidney exchange problem involving only 2-cycle and 3-cycle exchanges.First, we formal the kidney exchange problem as a parameterized model.And then we propose a randomized parameterized algorithm of running time O*(5.63k3 · 22k2) by randomly partitioning the vertices.Last, by using the random divide-and-conquer technique, another randomized algorithm of running time O* (k2”log k2/2.k3”logk3”/2.42k3.22k2) is given for the parameterized kidney problem.Moreover,our randomized algorithms can be extended to solve the general kidney exchange problem.
Kidney exchange problem Randomized algorithm Parameterized algorithm
Mugang Lin Jianxin Wang Qilong Feng
School of Information Science and Engineering,Central South University,Changsha 410083,China;Departm School of Information Science and Engineering,Central South University,Changsha 410083,China
国内会议
金华
英文
1-9
2015-10-30（万方平台首次上网日期，不代表论文的发表时间）