Kidney exchange and endless paths: On the optimal use of an altruistic donor

10/04/2020
by   Avrim Blum, et al.
0

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 with high probability, (3) simplifying previous analysis of this problem, and (4) extending results to the case of multiple altruistic donors.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset