SOBRA - Shielding Optimization for BRAchytherapy

• NP-Completeness and APX-Hardness • We prove that the problems MinFixMask OPT and MinFixMask BOUND are NP-complete. • We establish that FixMasks + is NP-complete and APX-hard. • We show NP-completeness of DFixMasks + . • Exact, FPT, and Approximation Algorithms for DFixMasks + • We design a fixed-parameter tractable (FPT) algorithm running in O *(2 M ) time, parameterized by the number of shield configurations M . • We present a polynomial-time 1 M -approximation algorithm. • We propose an exponential k M -approximation method (for a treatment plan length k ). • We provide a tight ( 1 − 1 e ) -approximation algorithm by exploiting monotonicity and submodularity of the objective function. • Quasi-Polynomial Algorithms and Logarithmic Approximations • We develop quasi-polynomial-time algorithms for MinFixMask OPT , MinFixMask OPT + , MinFixMask BOUND , and MinFixMask BOUND + , assuming that the maximum prescribed dose d ^ max is polynomially bounded. • Under the same assumption, we achieve polynomial-time approximation algorithms with a logarithmic factor log ( d ^ max ) for MinFixMask OPT and MinFixMask OPT + . • Polynomial-Time Solvable Special Cases • We identify polynomial-time solvable cases: FixMask and FixMasks + when M = 1 . • We show that the problems MinFixMask BOUND and MinFixMask BOUND + can be solved in polynomial time when T max 1, N ;. In this paper, we study a combinatorial problem which arises in the development of innovative treatment strategies and equipment using tunable shields in internal radiotherapy. From an algorithmic point of view, the problem is related to circular integer word decomposition into circular binary words under constraints. We consider several variants of the problem, depending on constraints and parameters and present exact, approximation, fixed parameter tractable algorithms and NP-hardness and APX-hardness results.