Exploring the complexity of the integer image problem in the max-algebra

详细信息    查看全文

• 作者：Marie MacCaig ^{m.maccaig.maths@outlook.com}
• 关键词：Max-algebra ; Integer vector ; Column span ; Image space ; Complexity
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P2
• 页码：261-275
• 全文大小：463 K
• 卷排序：217

文摘

We investigate the complexity of the problem of finding an integer vector in the max-algebraic column span of a matrix, which we call the integer image problem. We show some cases where we can determine in strongly polynomial time whether such an integer vector exists, and find such an integer vector if it does exist. On the other hand we also describe a group of related problems each of which we prove to be NP-hard. Our main results demonstrate that the integer image problem is equivalent to finding a special type of integer image of a matrix satisfying a property we call column typical. For a subclass of matrices this problem is polynomially solvable but if we remove the column typical assumption then it becomes NP-hard.