论文标题
肾脏交换和无尽的道路：最佳利用捐助者
Kidney exchange and endless paths: On the optimal use of an altruistic donor
论文作者
论文摘要
我们考虑了肾脏交换的经过良好研究的在线随机图模型，随着时间的流逝，代表患者唐纳对的节点到达，定向边缘的可能性为p。我们假设存在一个无私的捐助者，他在此图中充当定向捐赠路径的开始节点。算法问题是选择要执行哪些捐款，以及何时降低患者在接受肾脏之前必须等待的时间。 我们通过（1）以最佳的O（1/p）预期等待时间提供有效的（实际上是线性时间）算法的（实际上是线性时间）算法的理解，（2）表明，实际上某些算法为O（1/p）等待时间的所有患者提供了保证，并以较高的概率}的范围{\ em}简化了以前的案例，（3）供应了案例和（4）案例和（4）案例。
We consider a well-studied online random graph model for kidney exchange, where nodes representing patient-donor pairs arrive over time, and the probability of a directed edge is p. We assume existence of a single altruistic donor, who serves as a start node in this graph for a directed path of donations. The algorithmic problem is to select which donations to perform, and when, to minimize the amount of time that patients must wait before receiving a kidney. We advance our understanding of this setting by (1) providing efficient (in fact, linear-time) algorithms with optimal O(1/p) expected waiting time, (2) showing that some of these algorithms in fact provide guarantees to all patients of O(1/p) waiting time {\em with high probability}, (3) simplifying previous analysis of this problem, and (4) extending results to the case of multiple altruistic donors.
