RI: Medium: Algorithms for Robust Barter Exchanges, with Application to Kidneys

RI：媒介：稳健的易货交换算法，适用于肾脏

• 批准号: 0905390
• 负责人: Tuomas Sandholm
• 金额: $ 85.53万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-07-01 至 2012-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0905390&HistoricalAwards=false
• 关键词: RI; Medium; Algorithms; Robust; Barter

In the US alone, over 30,000 fall sick with lethal kidney disease each year, and over 77,000 await for a kidney transplant, many more than any other transplant. That demand far exceeds the supply of cadaver kidneys. It is possible for a living person to donate a kidney, e.g., to a relative or a friend, and both can live well. Unfortunately, it is unlikely that a given donor can donate to a given patient due to blood type and tissue type incompatibilities. This opens the door for kidney exchange. Consider two donor-patient pairs, A and B. Say that each of the pairs is incompatible. Yet Donor A may be able to donate to Patient B, and Donor B to Patient A. This constitutes a cycle of length two. Somewhat longer cycles are also practical. The principal investigator's prior research has proved that the exchange clearing problem is NP-complete, and developed an exchange algorithm that scales to the nationwide level. Research under this award is scaling up and expanding the functionality of the exchange algorithms to develop (a) faster exhange algorithms (e.g., through search-tree reorganization), (b) online algorithms for deciding which cycles to select in light of changing donors and recipients, (c) algorithms that are robust to last-minute failures, and (d) using machine learning to predict the survival duration of kidney transplants and failure probabilities of last-minute tests. Some of the techniques and theory developed to address these issues also apply to other combinatorial search problems.This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).

仅在美国，每年就有超过30，000人患有致命的肾脏疾病，超过77，000人等待肾脏移植，比任何其他移植都要多。这一需求远远超过了尸体肾脏的供应。一个活着的人可以捐献肾脏，例如，给亲戚或朋友，两个人都能过得很好。不幸的是，由于血型和组织类型不相容，给定的捐赠者不太可能捐赠给给定的患者。这为肾脏交换打开了大门。考虑两个供者-患者对，A和B。假设每一对都是不相容的。然而，捐献者A可能会捐献给患者B，而捐献者B可能会捐献给患者A。这就构成了一个长度为2的周期。稍微长一点的周期也是可行的。主要研究者的先前研究已经证明了交换清算问题是NP完全的，并开发了一个可扩展到全国范围的交换算法。该奖项下的研究正在扩大和扩展交换算法的功能，以开发（a）更快的交换算法（例如，通过搜索树重组），（B）根据变化的供体和受体决定选择哪些周期的在线算法，（c）对最后一分钟失败具有鲁棒性的算法，以及（d）使用机器学习来预测肾移植的存活时间和最后一分钟测试的失败概率。为解决这些问题而开发的一些技术和理论也适用于其他组合搜索问题。该奖项根据2009年美国复苏和再投资法案（公法111-5）资助。