Paper Info
Title
Decomposition of integer matrices and multileaf collimator sequencing
Abstract
In this paper, we consider the problem of decomposing an integer matrix into a weighted sum of binary matrices that have the strict consecutive ones property. This problem is motivated by an application in cancer radiotherapy planning, namely the sequencing of multileaf collimators to realize a given intensity matrix. In addition, we also mention another application in the design of public transportation. We are interested in two versions of the problem, minimizing the sum of the coefficients in the decomposition (decomposition time) and minimizing the number of matrices used in the decomposition (decomposition cardinality). We present polynomial time algorithms for unconstrained and constrained versions of the decomposition time problem and prove that the (unconstrained) decomposition cardinality problem is strongly NP-hard. For the decomposition cardinality problem, some polynomially solvable special cases are considered and heuristics are proposed for the general case.
Year
DOI
Venue
2005
10.1016/j.dam.2005.04.008
Discrete Applied Mathematics
Keywords
Field
DocType
binary matrix,decomposition of integer matrices,decomposition time,intensity matrix,cancer radiotherapy planning,decomposition time problem,weighted sum,radiotherapy,consecutive ones property,multileaf collimator sequencing,decomposition cardinality,polynomial time algorithm,decomposition cardinality problem,integer matrix,public transport
Integer,Discrete mathematics,Combinatorics,Matrix (mathematics),Matrix decomposition,Cardinality,Decomposition method (constraint satisfaction),Multileaf collimator,Time complexity,Integer matrix,Mathematics
Journal
Volume
Issue
ISSN
152
1-3
Discrete Applied Mathematics
Citations 
PageRank 
References 
44
2.51
6
Authors
4
Name
Order
Citations
PageRank
Davaatseren Baatar11439.87
Horst W. Hamacher256257.39
Matthias Ehrgott392360.59
Gerhard Woeginger44176384.37