On the integer max-linear programming problem

Peter Butkovic, Marie MacCaig

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)
187 Downloads (Pure)


Max-linear programs have been used to describe optimisation problems for multiprocessor interactive systems. In some instances the variables used in this model are required to be integer; however, no method seems to exist for finding integer solutions to max-linear programs.

For a generic class of matrices, we show that integer solutions to two-sided max-linear systems and programs can be found in polynomial time. For general matrices, we adapt the existing methods for finding real solutions to obtain algorithms for finding integer solutions.
Original languageEnglish
Pages (from-to)128–141
JournalDiscrete Applied Mathematics
Early online date13 Sept 2013
Publication statusPublished - 10 Jan 2014


  • Max-linear system
  • Integer vector
  • Max-linear program


Dive into the research topics of 'On the integer max-linear programming problem'. Together they form a unique fingerprint.

Cite this