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

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.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2017, 217 (2), pp.261--275. 〈10.1016/j.dam.2016.09.016〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01423520
Contributeur : Stephane Gaubert <>
Soumis le : jeudi 29 décembre 2016 - 23:31:21
Dernière modification le : jeudi 10 mai 2018 - 02:05:45

Identifiants

Citation

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〉

Partager

Métriques

Consultations de la notice

321