×

A network flow algorithm to minimize beam-on time for unconstrained multileaf collimator problems in cancer radiation therapy. (English) Zbl 1061.92033

Summary: We study the modulation of intensity matrices arising in cancer radiation therapy using multileaf collimators. This problem can be formulated by decomposing a given \(m \times 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 in which no technical constraints have to be taken into account. In this situation, the rows of the intensity matrix are independent of each other and the problem is equivalent to decomposing \(m\) intensity rows, independent of each other, into positive linear combinations of (0, 1) rows with the consecutive 1’s property.
We demonstrate that this problem can be transformed into a minimum cost flow problem in a directed network that has the following special structures: (1) the network is acyclic; (2) it is a complete graph (that is, there is an arc \((i, j)\) whenever \(i < j\)); (3) each arc cost is 1; and (4) each arc is uncapacitated (that is, it has infinite capacity). We show that using this special structure, the minimum cost flow problem can be solved in \(O(n)\) time. Because we need to solve m such problems, the total running time of our algorithm is \(O(nm)\), which is an optimal algorithm to decompose a given \(m \times n\) integer matrix into a positive linear combination of (0, 1) matrices.

MSC:

92C50 Medical applications (general)
90C05 Linear programming
90B10 Deterministic network models in operations research
15A99 Basic linear algebra
PDF BibTeX XML Cite
Full Text: DOI Link

References:

[1] and Network flows: Theory, algorithms, and applications, Prentice-Hall, Englewood Cliffs, NJ, 1993.
[2] New linear programming models for multileaf collimators in radiation therapy, Master’s thesis, Department of Mathematics, University of Kaiserslautern, Germany, 2002.
[3] and Fast linear programming models for constrained multileaf collimators in radiation therapy, Technical Report, Department of Mathematics, University of Kaiserslautern, Germany, 2003.
[4] and Decomposition of integer matrices into consecutive ones matrices and application, Research Report, Department of Mathematics, University of Kaiserslautern, Germany, 2004.
[5] Boland, Networks 43 pp 226– (2004)
[6] Bortfeld, Int J Radiat Oncol Biol Phys 28 pp 723– (1994)
[7] Open research question section of Oberwolfach conference, November 2002.
[8] and, ? A mixed integer programming approach to the multileaf collimator problem,? The use of computers in radiation therapy, and, (Editors), Springer-Verlag, Berlin, 2000, pp. 210-212.
[9] An integer programming approach to the multileaf collimator problem, Master’s Thesis, Department of Mathematics, University of Kaiserslautern, Germany, 2000.
[10] and Column generation for IMRT cancer therapy optimization with implementable segments, Ann Operat Res, 2004, submitted.
[11] Siochi, Int J Radiat Oncol Biol Phys 43 pp 671– (1999)
[12] Xia, Med Phys 25 pp 1424– (1998)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.