Decomposition of integer matrices and multileaf collimator sequencing (Q2576339)

A binary matrix is a (strict) \textit{consecutive ones matrix} if the ones occur consecutively in a single block in each row. Let \({\mathcal K}\) be an index set of all \(M\times N\) consecutive ones matrices and \({\mathcal K'}\subset {\mathcal K}\). The authors deal with the following problem. Given an \(M\times N\) matrix \(A=(a_{m,n})\) with nonnegative integer entries, find nonnegative integers \(\alpha_k\) and \(M\times N\) consecutive ones matrices \(Y^k\), where \(k\in {\mathcal K'}\), such that \(A=\sum_{k\in{\mathcal K'}} \alpha_kY^k.\) They are particularly interested in minimizing the sum of the coefficients in the decomposition and minimizing the number of matrices used in the decomposition. They develop several algorithms for achieving their goal in polynomial time under certain assumptions. There are applications to radiation therapy planning and stop design in public transportation.