TY - JOUR

T1 - Decomposition of integer matrices and multileaf collimator sequencing

AU - Baatar, D.

AU - Hamacher, H.W.

AU - Ehrgott, M.

AU - Woeginger, G.J.

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

U2 - 10.1016/j.dam.2005.04.008

DO - 10.1016/j.dam.2005.04.008

M3 - Article

SN - 0166-218X

VL - 152

SP - 6

EP - 34

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -