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

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Davaatseren Baatar
URN (permanent link):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 Publication:2005
Publishing Institute:Technische Universität Kaiserslautern
Granting Institute:Technische Universität Kaiserslautern
Acceptance Date of the Thesis:2005/08/25
Tag:Multileaf collimator; large scale integer programming
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:510 Mathematik
MSC-Classification (mathematics):90C06 Large-scale problems
90C11 Mixed integer programming

$Rev: 12793 $