Introduction to max-linear programming

Peter Butkovic, A Aminu

Research output: Contribution to journalArticle

24 Citations (Scopus)


Let a circle plus b = max(a, b) and a circle times b = a + b for a, b is an element of R. Extend this pair of operations to matrices and vectors in the same way as in linear algebra. Being motivated by scheduling of multiprocessor interactive systems, we introduce max-linear programs of the form f(T) circle times x -> min (or max) subject to A circle times x circle plus c = B circle times x circle plus d and develop solution methods for both of them. We prove that these methods are pseudopolynomial if all entries are integers. This result is based on an existing pseudo-polynomial algorithm for solving the systems of the form A circle times x = B circle times y.
Original languageEnglish
Pages (from-to)1-17
Number of pages17
JournalIMA Journal of Management Mathematics
Issue number3
Early online date5 Nov 2008
Publication statusPublished - 1 Jul 2009


  • max-linear programming
  • optimal solution
  • pseudo-polynomial algorithm


Dive into the research topics of 'Introduction to max-linear programming'. Together they form a unique fingerprint.

Cite this