×

Randomized parameterized algorithms for the kidney exchange problem. (English) Zbl 1461.90122

Summary: In order to increase the potential kidney transplants between patients and their incompatible donors, kidney exchange programs have been created in many countries. In the programs, designing algorithms for the kidney exchange problem plays a critical role. The graph theory model of the kidney exchange problem is to find a maximum weight packing of vertex-disjoint cycles and chains for a given weighted digraph. In general, the length of cycles is not more than a given constant \(L\) (typically \(2 \leq L \leq 5\)), and the objective function corresponds to maximizing the number of possible kidney transplants. In this paper, we study the parameterized complexity and randomized algorithms for the kidney exchange problem without chains from theory. We construct two different parameterized models of the kidney exchange problem for two cases \(L = 3\) and \(L \geq 3\), and propose two randomized parameterized algorithms based on the random partitioning technique and the randomized algebraic technique, respectively.

MSC:

90C27 Combinatorial optimization
68W20 Randomized algorithms
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
90C15 Stochastic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Rapaport, F.T.; The case for a living emotionally related international kidney donor exchange registry; Transpl. Proc.: 1986; Volume 18 ,5-9.
[2] Constantino, M.; Klimentova, X.; Viana, A.; Rais, A.; New insights on integer-programming models for the kidney exchange problem; Eur. J. Oper. Res.: 2013; Volume 231 ,57-68. · Zbl 1317.90174
[3] Abraham, D.J.; Blum, A.; Sandholm, T.; Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges; Proceedings of the 8th ACM Conference on Electronic Commerce: ; ,295-304.
[4] Biró, P.; Manlove, D.F.; Rizzi, R.; Maximum weight cycle packing in directed graphs, with application to kidney exchange programs; Discrete Math. Algorithms Appl.: 2009; Volume 1 ,499-517. · Zbl 1194.05121
[5] Roth, A.E.; Sönmez, T.; Ünver, M.U.; Efficient kidney exchange: Coincidence of wants in markets with compatibility-based preferences; Am. Econ. Rev.: 2007; Volume 97 ,828-851.
[6] Roth, A.E.; Sönmez, T.; Ünver, M.U.; Kidney exchange; Q. J. Econ.: 2004; Volume 119 ,457-488. · Zbl 1064.92029
[7] Segev, D.L.; Gentry, S.E.; Warren, D.S.; Reeb, B.; Montgomery, R.A.; Kidney paired donation and optimizing the use of live donor organs; JAMA: 2005; Volume 293 ,1883-1890.
[8] Xiao, M.; Wang, X.; Exact algorithms and complexity of kidney exchange; Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence: ; ,555-561.
[9] Ashlagi, I.; Gilchrist, D.S.; Roth, A.E.; Rees, M.A.; Nonsimultaneous chains and dominos in kidney-paired donation-Revisited; Am. J. Transpl.: 2011; Volume 11 ,984-994.
[10] Glorie, K.M.; van de Klundert, J.J.; Wagelmans, A.P.M.; Kidney exchange with long chains: an efficient pricing algorithm for clearing barter exchanges with branch-and-price; Manuf. Serv. Oper. Manag.: 2014; Volume 16 ,498-512.
[11] Anderson, R.; Ashlagi, I.; Gamarnik, D.; Roth, A.E.; Finding long chains in kidney exchange using the traveling salesman problem; Proc. Natl. Acad. Sci. USA: 2015; Volume 112 ,663-668.
[12] Manlove, D.F.; O’malley, G.; Paired and altruistic kidney donation in the UK: algorithms and experimentation; J. Exp. Algorithmics: 2015; Volume 19 ,6:1-6:21.
[13] Gentry, S.E.; Montgomery, R.A.; Segev, D.L.; Kidney paired donation: Fundamentals, limitations, and expansions; Am. J. Kidney Dis.: 2011; Volume 57 ,144-151.
[14] Huang, C.; Circular stable matching and 3-way kidney transplant; Algorithmica: 2010; Volume 58 ,137-150. · Zbl 1204.68146
[15] Barnhart, C.; Johnson, L.E.; Nemhauser, G.L.; Savelsbergh, M.W.; Vance, P.H.; Branch-and-price: column generation for solving huge integer programs; Oper. Res.: 1998; Volume 46 ,316-329. · Zbl 0979.90092
[16] Klimentova, X.; Alvelos, F.; Viana, A.; A new branch-and-price approach for the kidney exchange problem; Proceedings of the 14th International Conference on Computational Science and Its Applications: ; ,237-252.
[17] Dantzig, G.; Wolfe, P.; Decomposition principle for linear programs; Oper. Res.: 1960; Volume 8 ,101-111. · Zbl 0093.32806
[18] Dickerson, J.P.; Manlove, D.F.; Plaut, B.; Sandholm, T.; Trimble, J.; Position-indexed formulations for kidney exchange; Proceedings of the 2016 ACM Conference on Economics and Computation: ; ,25-42.
[19] Mak-Hau, V.; A polyhedral study of the cardinality constrained multi-cycle and multi-chain problem on directed graphs; Comput. Oper. Res.: 2018; Volume 99 ,13-26. · Zbl 1458.90615
[20] Mak-Hau, V.; On the kidney exchange problem: Cardinality constrained cycle and chain problems on directed graphs: A survey of integer programming approaches; J. Comb. Optim.: 2017; Volume 33 ,35-59. · Zbl 1366.90180
[21] Luo, S.; Tang, P.; Wu, C.; Zeng, J.; Approximation of barter exchanges with cycle length constraints; arXiv: 2018; .
[22] Jia, Z.; Tang, P.; Wang, R.; Zhang, H.; Efficient near-optimal algorithms for barter exchange; Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems: ; ,362-370.
[23] Dickerson, J.P.; Kazachkov, A.M.; Procaccia, A.D.; Sandholm, T.; Small representations of big kidney exchange graphs; Proceedings of the 31st AAAI Conference on Artificial Intelligence: ; ,487-493.
[24] Chen, J.; Liu, Y.; Lu, S.; Sze, S.H.; Zhang, F.; Iterative expansion and color coding: An improved algorithm for 3D-matching; ACM T. Algorithms: 2012; Volume 8 ,6. · Zbl 1295.68231
[25] Feng, Q.; Wang, J.; Li, S.; Chen, J.; Randomized parameterized algorithms for P2-Packing and Co-Path Packing problems; J. Comb. Optim.: 2015; Volume 29 ,125-140. · Zbl 1327.90256
[26] Björklund, A.; Determinant sums for undirected hamiltonicity; Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science: ; ,173-182. · Zbl 1292.05244
[27] Koutis, I.; Faster algebraic algorithms for path and packing problems; Proceedings of the 35th International Colloquium on Automata, Languages and Programming: ; ,575-586. · Zbl 1153.68562
[28] Koutis, I.; Williams, R.; Limits and applications of group algebras for parameterized problems; Proceedings of the 36th International Colloquium on Automata, Languages and Programming: ; ,653-664. · Zbl 1248.68251
[29] Williams, R.; Finding paths of length k in O*(2k) time; Inform. Process. Lett.: 2009; Volume 109 ,315-318. · Zbl 1191.68857
[30] Assadi, S.; Khanna, S.; Li, Y.; The stochastic matching problem with (very) few queries; Proceedings of the 2016 ACM Conference on Economics and Computation: ; ,43-60.
[31] Chen, N.; Immorlica, N.; Karlin, A.R.; Mahdian, M.; Rudra, A.; Approximating matches made in heaven; Proceedings of 36th International Colloquium on Automata, Languages and Programming: ; ,266-278. · Zbl 1247.05237
[32] Awasthi, P.; Sandholm, T.; Online stochastic optimization in the large: Application to kidney exchange; Proceedings of the 21st International Joint Conference on Artificial Intelligence: ; ,405-411.
[33] Fang, W.; Filos-Ratsikas, A.; Frederiksen, S.K.S.; Tang, P.; Zuo, S.; Randomized assignments for barter exchanges: Fairness vs; efficiency. In Proceedings of the 4th International Conference on Algorithmic Decision Theory: ; ,537-552. · Zbl 1405.91473
[34] Goyal, P.; Misra, N.; Panolan, F.; Zehavi, M.; Deterministic algorithms for matching and packing problems based on representative sets; SIAM J. Discrete Math.: 2015; Volume 29 ,1815-1836. · Zbl 1330.68111
[35] Downey, R.G.; Fellows, M.R.; ; Parameterized Complexity: Berlin, Germany 1999; .
[36] Cygan, M.; Fomin, F.V.; Kowalik, Ł.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S.; ; Parameterized Algorithms: Berlin, Germany 2015; .
[37] Gabow, H.N.; Data structures for weighted matching and nearest common ancestors with linking; Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms: ; ,434-443. · Zbl 0800.68617
[38] Hanto, R.L.; Saidman, S.; Roth, A.E.; Delmonico, F.; The evolution of a successful kidney paired donation program; Transplantation: 2010; Volume 90 ,940.
[39] Edmonds, J.; Maximum matching and a polyhedron with 0, 1-vertices; J. Res. Nat. Bur. Stand. Sec. B: 1965; Volume 69 ,125-130. · Zbl 0141.21802
[40] Björklund, A.; Husfeldt, T.; Kaski, P.; Koivisto, M.; Narrow sieves for parameterized paths and packings; J. Comput. Syst. Sci.: 2017; Volume 87 ,119-139. · Zbl 1370.68321
[41] Fomin, F.V.; Lokshtanov, D.; Raman, V.; Saurabh, S.; Rao, B.V.R.; Faster algorithms for finding and counting subgraphs; J. Comput. Syst. Sci.: 2012; Volume 78 ,698-706. · Zbl 1246.05149
[42] Tarjan, R.; Depth-First Search and Linear Graph Algorithms; SIAM J. Comput.: 1972; Volume 1 ,146-160. · Zbl 0251.05107
[43] Cechlárová, K.; Fleiner, T.; Manlove, D.F.; The kidney exchange game; Proceedings of the 8th International Symposium on Operational Research: ; ,77-83. · Zbl 1142.91385
[44] Cechlárová, K.; Biró, P.; Inapproximability of the kidney exchange problem; Inform. Process. Lett.: 2007; Volume 101 ,199-202.
[45] Biró, P.; McDermid, E.; Three-sided stable matchings with cyclic preferences; Algorithmica: 2010; Volume 58 ,5-18. · Zbl 1205.68257
[46] Cechlárová, K.; Lacko, V.; The kidney exchange problem: How hard is it to find a donor?; Ann. Oper. Res.: 2012; Volume 193 ,255-271. · Zbl 1254.91069
[47] Mészáros-Karkus, Z.; Hardness results for stable exchange problems; Theor. Comput. Sci.: 2017; Volume 670 ,68-78. · Zbl 1359.68111
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.