Projects per year
Abstract
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 maxlinear 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 pseudopolynomial algorithm for solving the systems of the form A circle times x = B circle times y.
Original language  English 

Pages (fromto)  117 
Number of pages  17 
Journal  IMA Journal of Management Mathematics 
Volume  20 
Issue number  3 
Early online date  5 Nov 2008 
DOIs  
Publication status  Published  1 Jul 2009 
Keywords
 maxlinear programming
 optimal solution
 pseudopolynomial algorithm
Fingerprint
Dive into the research topics of 'Introduction to maxlinear programming'. Together they form a unique fingerprint.Projects
 1 Finished

Feasibility and Reachability in MaxLinear Systems
Butkovic, P.
Engineering & Physical Science Research Council
1/02/08 → 30/04/11
Project: Research Councils