On integer images of max-plus linear mappings
On integer images of max-plus linear mappings
复制标题
关于最大加线性映射的整数图像
DOI：
10.1016/j.dam.2018.01.001
复制
发表时间：
2018
影响因子：
1.1
通讯作者：
Butkovic P
中科院分区：
文献类型：
--
作者：
Butkovic P
让我们以与传统线性代数中相同的方式将运算对λ，λ = max，+在真实的数上扩展到矩阵。研究了映射x→ A <$x的整数象，其中A∈ Rm × n，x∈ Rn.对于至少一个x∈ Rn，A_∞ x是否为整数向量的问题已经研究了一段时间，但多项式求解方法似乎只存在于特殊情况下。在术语组合矩阵理论这个问题读：是否有可能增加常数列的一个给定的矩阵，使所有行的最大值是整数？这个问题的动机是试图解决一类作业调度问题。我们提出了两个多项式可解的特殊情况下，旨在更接近多项式的解决方案的方法在一般情况下。
Let us extend the pair of operations⊕,⊗= max,+ over real numbers to matrices in the same way as in conventional linear algebra. We study integer images of mappings x→ A⊗ x, where A∈ R m× n and x∈ R n. The question whether A⊗ x is an integer vector for at least one x∈ R n has been studied for some time but polynomial solution methods seem to exist only in special cases. In the terminology of combinatorial matrix theory this question reads: is it possible to add constants to the columns of a given matrix so that all row maxima are integer? This problem has been motivated by attempts to solve a class of job-scheduling problems. We present two polynomially solvable special cases aiming to move closer to a polynomial solution method in the general case.