Approximated MLC shape matrix decomposition with interleaf collision constraint

Shape matrix decomposition is a subproblem in radiation therapy planning. A given fluence matrix A has to be decomposed into a sum of shape matrices corresponding to homogeneous fields that can be shaped by a multileaf collimator (MLC). We solve the problem of minimizing the delivery time for an approximation of A satisfying certain prescribed bounds, under the additional condition that the used MLC requires the interleaf collision constraint. Key words: Intensity modulated radiation therapy (IMRT); multileaf collimator; combinatorial optimization; programming involving graphs 1