Randomized Algorithms for Mixed Matching and Covering in Hypergraphs in 3D Seed Reconstruction in Brachytherapy
Brachytherapy is a method developed in the 1980s for cancer radiation in organs like prostate, lung, or breast. At the Clinic of Radiotherapy (radiooncology), Christian Albrechts University of Kiel, among others, low dose radiation therapy (LDR therapy) for the treatment of prostate cancer is applied, where 25-80 small radioactive seeds are implanted in the affected organ. For the quality control of the treatment plan the locations of the seeds after the operation have to be checked. This is done by taking usually 3 X-ray photographs from three different angles (so-called 3-film technique). On the films the seeds appear as white lines. To determine the positions of the seeds in the organ the task now is to match the 3 different images (lines) representing the same seed. In this paper we first model the seed reconstruction problem as a minimum-weight perfect matching problem in a hypergraph and based on this as an integer linear program. To solve this integer program, an algorithm based on the so-called randomized rounding scheme introduced by Raghavan and Thompson (1987) is designed and applied. This algorithm is not only very fast, but accessible at least in part for a mathematical rigorous analysis. We give a partial analysis of the algorithm combining probabilistic and combinatorial methods, which shows that in the worst-case the solution produced is in some strong sense close to a minimum-weight perfect matching.