KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Wed, 28 Oct 2015 14:33:01 +0100Wed, 28 Oct 2015 14:33:01 +0100Minimizing the Number of Apertures in Multileaf Collimator Sequencing with Field Splitting
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4206
In this paper we consider the problem of decomposing a given integer matrix A into
a positive integer linear combination of consecutive-ones matrices with a bound on the
number of columns per matrix. This problem is of relevance in the realization stage
of intensity modulated radiation therapy (IMRT) using linear accelerators and multileaf
collimators with limited width. Constrained and unconstrained versions of the problem
with the objectives of minimizing beam-on time and decomposition cardinality are considered.
We introduce a new approach which can be used to find the minimum beam-on
time for both constrained and unconstrained versions of the problem. The decomposition
cardinality problem is shown to be NP-hard and an approach is proposed to solve the
lexicographic decomposition problem of minimizing the decomposition cardinality subject
to optimal beam-on time.Horst W. Hamacher; Ines M. Raschendorfer; Davaatseren Baatar; Matthias Ehrgottpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4206Wed, 28 Oct 2015 14:33:01 +0100Minimizing the Number of Apertures in Multileaf Collimator Sequencing with Field Splitting
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4197
In this paper we consider the problem of decomposing a given integer matrix A into
a positive integer linear combination of consecutive-ones matrices with a bound on the
number of columns per matrix. This problem is of relevance in the realization stage
of intensity modulated radiation therapy (IMRT) using linear accelerators and multileaf
collimators with limited width. Constrained and unconstrained versions of the problem
with the objectives of minimizing beam-on time and decomposition cardinality are considered.
We introduce a new approach which can be used to find the minimum beam-on
time for both constrained and unconstrained versions of the problem. The decomposition
cardinality problem is shown to be NP-hard and an approach is proposed to solve the
lexicographic decomposition problem of minimizing the decomposition cardinality subject
to optimal beam-on time.Davaatseren Baatar; Matthias Ehrgott; Horst W. Hamacher; Ines M. Raschendorferarticlehttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4197Fri, 16 Oct 2015 11:00:21 +0200Matrix Decomposition with Times and Cardinality Objectives: Theory, Algorithms and Application to Multileaf Collimator Sequencing
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1721
In this thesis we have discussed the problem of decomposing an integer matrix \(A\) into a weighted sum \(A=\sum_{k \in {\mathcal K}} \alpha_k Y^k\) of 0-1 matrices with the strict consecutive ones property. We have developed algorithms to find decompositions which minimize the decomposition time \(\sum_{k \in {\mathcal K}} \alpha_k\) and the decomposition cardinality \(|\{ k \in {\mathcal K}: \alpha_k > 0\}|\). In the absence of additional constraints on the 0-1 matrices \(Y^k\) we have given an algorithm that finds the minimal decomposition time in \({\mathcal O}(NM)\) time. For the case that the matrices \(Y^k\) are restricted to shape matrices -- a restriction which is important in the application of our results in radiotherapy -- we have given an \({\mathcal O}(NM^2)\) algorithm. This is achieved by solving an integer programming formulation of the problem by a very efficient combinatorial algorithm. In addition, we have shown that the problem of minimizing decomposition cardinality is strongly NP-hard, even for matrices with one row (and thus for the unconstrained as well as the shape matrix decomposition). Our greedy heuristics are based on the results for the decomposition time problem and produce better results than previously published algorithms.Davaatseren Baatardoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1721Thu, 23 Mar 2006 15:23:30 +0100Decomposition of Integer Matrices and Multileaf Collimator Sequencing
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1582
In this paper we consider the problem of decomposing an integer matrix into a weighted sum of binary matrices that have to strict consecutive ones property.Davaatseren Baatar; Horst W. Hamacher; Matthias Ehrgott; Gerhard J. Woegingerpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1582Mon, 08 Nov 2004 11:12:15 +0100