# Randomized Parameterized Algorithms for the Kidney Exchange Problem
## 1 Introduction
In a chain exchange, if the donor of a patient-donor pair backs out of the chain after his patient has received a transplant, no pair in the remaining tail of the planned chain suffers irreparable harm. Hence, a chain exchange can be conducted non-simultaneously [9] and the length of a chain exchange can be much longer than that of a cycle exchange [10; 11]. But a donor in a non-simultaneous exchange still has the risk of reneging, which can make some patient-donor pairs lose exchange opportunity, thus in some literatures the limitation of chain length is still considered, e.g., the same length constrained for chains and cycles in [12]. An altruistic donor can be seen as a patient-donor pair with a \"dummy\" patient which is compatible with each donor of other incompatible patient-donor pairs. Thus, in this way, chain exchange and cycle exchange can be treated similarly in optimization models. In this paper, we mainly address the KEP without chains. Over the past decades, there has been a rich literature on models, market mechanisms, and optimal algorithms for the KEP. There are many different variations of the KEP when considering different scenarios and limitations. The reader is referred to surveys on KEP variants [2; 13]. In this section, we mainly describe the previous work of the KEP from a computational point of view. The complexity of the KEP was investigated in [3; 4], and [14]. When \(L\geq 3\), the KEP is NP-hard, meaning that it is unlikely there exists a polynomial time exact algorithm. For the KEP, most exact algorithms are based on Integer Programming (IP) approaches, and research work focuses mainly on IP formulations. [PERSON] et al. [5] proposed two noncompact formulations of IP for the KEP: the edge formulation and the cycle formulation with exponential numbers of constraints and variables, respectively. [PERSON] et al. [3] compared the two formulations and showed that the cycle formulation is tighter than the edge formulation when the cycle size is limited. They presented an incremental formulation approach to solve the cycle formulation based on enhancing the column generation method and the branch-and-price search technique [15]. To reduce the number of constraints and variables of the two formulations from exponential to polynomial, [PERSON] et al. [2] gave two compact formulations for the KEP: the edge assignment formulation and the extended edge formulation, and showed by computational analysis that when the scale of KEP becomes large, the compact formulations have more merits than non-compact ones. [PERSON] et al. [16] presented the disaggregated cycle decomposition model which is regarded as a Dantzig-Wolfe decomposition [17] of the extended edge formulation proposed in [2], and solved the model by a branch-and-price method. Recently, [PERSON] et al. [18] introduced models where chains are represented by only a polynomial number of position-indexed edge variables which bring about great improvements on running time for the KEP with chains. [PERSON] [19] studied the edge formulations for the KEP with and without chains and presented some polyhedral results. For a detailed review of various IP approaches to solving the KEP, see a recent survey of [PERSON] [20]. Approximation technique is also one of the main approaches of solving the KEP. [PERSON] et al. [4] proved the APX-completeness of the maximum size KEP when \(L=3\), and gave an \((L-1+\epsilon)\)-approximation algorithm for the maximum cycle weight KEP and an \((L/2+\epsilon)\)-approximation algorithm for the maximum size KEP (for any \(\epsilon>0\)). [PERSON] et al. [21] proved three inapproximability results for the KEP in a weighted graph. It is NP-hard to approximate the KEP within \(\frac{14}{13}\) under a fixed integer \(L>3\) and within \(\frac{434}{433}\) when \(L=3\). In an unweighted graph, it is NP-hard to approximate the KEP within \(\frac{698}{697}\) when \(L=3\). [PERSON] et al. [22] presented near optimal approximation algorithms by combining heuristics and local search technique.