Decomposition of integer matrices and multileaf collimator sequencing
Decomposition of integer matrices and multileaf collimator sequencing
复制标题
DOI：
10.1016/j.dam.2005.04.008
复制
发表时间：
2005-11-01
影响因子：
1.1
通讯作者：
Woeginger, GJ
中科院分区：
文献类型：
--
作者：
Baatar, D;Hamacher, HW;Woeginger, GJ
本文研究了将整数矩阵分解为具有严格连续1性质的二元矩阵加权和的问题。这个问题的动机是癌症放射治疗计划中的应用，即多叶准直器的测序以实现给定的强度矩阵。此外，我们还提到了在公共交通设计中的另一个应用。我们感兴趣的两个版本的问题，最小化的系数在分解（分解时间）和最小化的分解中使用的矩阵（分解基数）的数量的总和。我们提出了多项式时间算法的无约束和约束版本的分解时间问题，并证明（无约束）分解基数问题是强NP-困难的。对于分解基数问题，考虑了一些多项式可解的特殊情况，并提出了一般情况下的分解方法。(c)2005 Elsevier B.V.保留所有权利。
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. (c) 2005 Elsevier B.V. All rights reserved.