| 引用本文: | 王刚,骆志刚.多捐赠者肾脏调换问题.[J].国防科技大学学报,2013,35(6):132-137.[点击复制] |
| WANG Gang,LUO Zhigang.The multi-donor kidney exchange problem[J].Journal of National University of Defense Technology,2013,35(6):132-137[点击复制] |
|
| |
|
|
| 本文已被：浏览 7092次 下载 6493次 |
| 多捐赠者肾脏调换问题 |
| 王刚, 骆志刚 |
|
(国防科技大学 计算机学院，湖南 长沙 410073)
|
| 摘要: |
| 用于器官移植的肾脏处于严重的短缺状态。为缓解这一问题，越来越多的国家开始实施各种形式的肾脏调换计划。肾脏调换问题一般被建模为一个合作博弈(Kidney Exchange game, KE)。其中的局中人为病人及与其配型失败的捐赠者所构成的二元组。现实中不乏拥有多个配型捐赠者失败的病人。定义了多捐赠者肾脏调换博弈(Multi Donor Kidney Exchange game, MDKE)，分析了其可行解及稳定解的结构，证明了捐赠多颗肾脏无益于参与稳定调换，将TTC算法、KE稳定解的NP难解性以及最大覆盖稳定解的不可近似性拓展到MDKE。实验表明引入MDKE效果显著。 |
| 关键词: 肾脏调换 合作博弈 核心 稳定解 圈包装 |
| DOI： |
| 投稿日期：2013-03-07 |
| 基金项目: |
|
| The multi-donor kidney exchange problem |
| WANG Gang, LUO Zhigang |
|
(College of Computer, National University of Defense Technology, Changsha 410073, China)
|
| Abstract: |
| The kidney for transplantation is in serious shortage. To alleviate this problem, more and more countries have started various kidney exchange programs. The kidney exchange problem (KE) is generally modeled as a cooperative game. Each player represents an incompatible patient-donor pair. A patient may have more than one incompatible donor in reality. In light of this, the multi-donor kidney exchange game (MDKE) was defined. The structures of MDKE's feasible solutions and stable solutions were studied. It was proved that donating multiple kidneys is useless in joining in a better stable solution. Furthermore, the TTC algorithm, the NP-hardness of a stable solution and the inapproximability of a maximum cover stable solution of KE were extended to MDKE. Experiments show the effectiveness of MDKE. |
| Keywords: kidney exchange cooperative game core stable solution cycle packing |
|
|
