Randomized parameterized algorithms for the kidney exchange problem (Q2632525)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Randomized parameterized algorithms for the kidney exchange problem |
scientific article |
Statements
Randomized parameterized algorithms for the kidney exchange problem (English)
0 references
14 May 2019
0 references
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.
0 references
kidney exchange problem
0 references
randomized algorithm
0 references
parameterized algorithm
0 references
random partitioning
0 references
multilinear monomial detection
0 references
0 references
0 references
0 references