Projects per year
Abstract
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 maxplus linear mappings. The question whether Ax (in the maxplus 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 jobscheduling problems.
We present two polynomially solvable special cases aiming to move closer to a polynomial solution method in the general case.
We study integer images of maxplus linear mappings. The question whether Ax (in the maxplus 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 jobscheduling problems.
We present two polynomially solvable special cases aiming to move closer to a polynomial solution method in the general case.
Original language  English 

Pages (fromto)  6274 
Journal  Discrete Applied Mathematics 
Volume  239 
Early online date  1 Feb 2018 
DOIs  
Publication status  Published  20 Apr 2018 
Keywords
 maxlinear mapping
 integer image
 computational complexity
Fingerprint
Dive into the research topics of 'On integer images of maxplus linear mappings'. Together they form a unique fingerprint.Projects
 1 Finished

PerronFrobenius Theory and MaxAlgebraic Combinatorics of Nonnegative Matrices
Butkovic, P.
Engineering & Physical Science Research Council
12/03/12 → 11/03/14
Project: Research Councils