Matrix Decomposition with Times and Cardinality Objectives: Theory, Algorithms and Application to Multileaf Collimator Sequencing
- 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.
- Matrix-Zerlegung mit Zeit- und Kardinalitätszielfunktionen: Theorie, Algorithmen und Anwendung für Multileaf Collimator Sequencing
Author: | Davaatseren Baatar |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-19362 |
Advisor: | Horst W. Hamacher |
Document Type: | Doctoral Thesis |
Language of publication: | English |
Year of Completion: | 2005 |
Year of first Publication: | 2005 |
Publishing Institution: | Technische Universität Kaiserslautern |
Granting Institution: | Technische Universität Kaiserslautern |
Acceptance Date of the Thesis: | 2005/08/25 |
Date of the Publication (Server): | 2006/03/23 |
Tag: | Multileaf collimator; large scale integer programming |
Faculties / Organisational entities: | Kaiserslautern - Fachbereich Mathematik |
DDC-Cassification: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
MSC-Classification (mathematics): | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C06 Large-scale problems |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming | |
Licence (German): | Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011 |