A Kidney Exchange Matching Application Using the Blossom and Hungarian Algorithms for Pairwise and Multiway Matching

Abstract
Background/objectives: Patients of kidney failure sometimes have incompatible donors. This study proposes an application to get the best matchings based on scoring data.

Methods: For pairwise matching, we created a new graph from the original scoring matrix. This graph ensures pairwise matchings. To find an optimal matching, we used the Blossom algorithm. For multiway matching, we interpreted the scoring matrix as an assignment problem. For this, we used the Hungarian algorithm. The application was created using Python, NetworkX, NumPy, and PySimpleGUI. The app uses CSV files as input.

Findings: Both algorithms made for polynomial run times. Matching is fast and is guaranteed to be optimal. The application itself gets instantaneous results even for large donor-patient matrices.

Application/improvement: Hospitals or organizations can use this application for their kidney matching programs.

Keywords: Blossom Algorithm, Hungarian Algorithm, Kidney Failure, Donor Matching