Skip to Main content Skip to Navigation
Journal articles

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

Marie Maccaig 1, 2, 3
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France
Abstract : 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.
Document type :
Journal articles
Complete list of metadata
Contributor : Stephane Gaubert <>
Submitted on : Thursday, December 29, 2016 - 11:31:21 PM
Last modification on : Friday, April 30, 2021 - 9:52:03 AM

Links full text



Marie Maccaig. Exploring the complexity of the integer image problem in the max-algebra. Discrete Applied Mathematics, Elsevier, 2017, 217 (2), pp.261--275. ⟨10.1016/j.dam.2016.09.016⟩. ⟨hal-01423520⟩



Record views