Discrete approximations to real-valued leaf sequencing problems in radiation therapy

For a given m×nm×n nonnegative real matrix AA, a segmentation with 1-norm relative error ee is a set of pairs (α,S)={(α1,S1),(α2,S2),…,(αk,Sk)}(α,S)={(α1,S1),(α2,S2),…,(αk,Sk)}, where each αiαi is a positive number and SiSi is an m×nm×n binary matrix, and e=|A−∑i=1kαiSi|1/|A|1, where |A|1|A|1 is the 1-norm of a vector which consists of all the entries of the matrix AA. In certain radiation therapy applications, given AA and positive scalars γ,δγ,δ, we consider the optimization problem of finding a segmentation (α,S)(α,S) that minimizes z=∑i=1kαi+γk+δe subject to certain constraints on SiSi. This problem poses a major challenge in preparing a clinically acceptable treatment plan for Intensity Modulated Radiation Therapy (IMRT) and is known to be NP-hard. Known discrete IMRT algorithms use alternative objectives for this problem and an LL-level entrywise approximation Ā (i.e. each entry in AA is approximated by the closest entry in a set of LL equally-spaced integers), and produce a segmentation that satisfies Ā=∑i=1kᾱiSi. In this paper we present two algorithms that focus on the original non-discretized intensity matrix and consider measures of delivery quality and complexity (∑αi+γk)(∑αi+γk) as well as approximation error ee. The first algorithm uses a set partitioning approach to approximate AA by a matrix Ā that leads to segmentations with smaller kk for a given ee. The second algorithm uses a constrained least square approach to post-process a segmentation {(ᾱi,Si)} of Ā to replace ᾱi with real-valued αiαi in order to reduce kk and ee.