On the integer max-linear programming problem

Peter Butkovic, Marie MacCaig

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)
187 Downloads (Pure)

Abstract

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
Volume162
Early online date13 Sept 2013
DOIs
Publication statusPublished - 10 Jan 2014

Keywords

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

Fingerprint

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

Cite this