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

For a given m×n nonnegative real matrix A, a segmentation with 1-norm relative error e is a set of pairs (α,S)={(α₁,S₁),(α₂,S₂),…,(α_k,S_k)}, where each α_i is a positive number and S_i is an m×n binary matrix, and , where |A|₁ is the 1-norm of a vector which consists of all the entries of the matrix A. In certain radiation therapy applications, given A and positive scalars γ,δ, we consider the optimization problem of finding a segmentation (α,S) that minimizes subject to certain constraints on S_i. 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 L-level entrywise approximation (i.e. each entry in A is approximated by the closest entry in a set of L equally-spaced integers), and produce a segmentation that satisfies . 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) as well as approximation error e. The first algorithm uses a set partitioning approach to approximate A by a matrix that leads to segmentations with smaller k for a given e. The second algorithm uses a constrained least square approach to post-process a segmentation of to replace with real-valued α_i in order to reduce k and e.