Minimizing Beam-On Time in Radiation Treatment using Network Flows

In this paper, we study the modulation of intensity matrices arising in cancer radiation therapy using multileaf collimators. This problem can be formulated as decomposing a given m×n integer matrix into a positive linear combination of (0,1) matrices with the strict consecutive 1’s property in rows. We consider a special case when the rows of the intensity matrix can be independently decomposed, in which case the problem is equivalent to m independent problems of decomposing an intensity row into a positive linear combination of (0, 1) rows with the consecutive 1’s property. We show that this problem can be transformed into a minimum cost flow problem in a directed network which has the following special structures: (i) the network is a complete acyclic graph (that is, there is an arc (i, j) whenever i < j); (ii) each arc cost is 1; and (iii) each arc is uncapacitated (that is, has infinite capacity). We show that using this special structure, the minimum cost flow problem can be solved in O(n) time. Since we need to solve m such problems, the total running time of our algorithm is O(nm) time, which is an optimal algorithm to decompose a given m×n integer matrix into a positive linear combination of (0,1) matrices. 1 Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611 2 Fachbereich Mathematik, Universitaet Kaiserslautern, D-67653 Kaiserslautern, Germany