On integer images of max-plus linear mappings

Peter Butkovic

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
141 Downloads (Pure)


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 max-plus linear mappings. The question whether Ax (in the max-plus algebra) is an integer vector for at least one x 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.
Original languageEnglish
Pages (from-to)62-74
JournalDiscrete Applied Mathematics
Early online date1 Feb 2018
Publication statusPublished - 20 Apr 2018


  • max-linear mapping
  • integer image
  • computational complexity


Dive into the research topics of 'On integer images of max-plus linear mappings'. Together they form a unique fingerprint.

Cite this