Projects per year
Abstract
This paper is a contribution to the study of finite, twosided maxlinear systems Ax = Bx over the maxplus algebra. These systems are known to be equivalent to meanpayoff games and the problem of deciding whether or not a nontrivial solution exists is in NP ∩ co − NP. Yet, no polynomial solution method seems to be known to date.
We study two special types of these systems with square matrices A and B. The first type, called minimally active, is defined by the requirement that for every nontrivial solution x, the maximum on each side of every equation is attained exactly once. For the second type, called essential systems, we require that every component of any nontrivial solution is active on at least one side of at least one equation. Minimally active systems are shown to be a special case of essential systems and it is shown that all essential systems can be reduced
to minimally active ones. Essential systems are equivalently defined as those square finite systems for which all nontrivial solutions are finite.
We prove that in every solvable twosided maxlinear system of minimally active or essential type, all positions in C := A ⊕ B active in any optimal permutation for the assignment problem for C, are also active for some nontrivial solution (any nontrivial solution in the minimally active case) of the twosided system. This enables us to deduce conditions on a solution x for which it is possible in some cases to find x in polynomial time. It is also proved that any essential system can be transformed to a minimally active system in polynomial time.
We study two special types of these systems with square matrices A and B. The first type, called minimally active, is defined by the requirement that for every nontrivial solution x, the maximum on each side of every equation is attained exactly once. For the second type, called essential systems, we require that every component of any nontrivial solution is active on at least one side of at least one equation. Minimally active systems are shown to be a special case of essential systems and it is shown that all essential systems can be reduced
to minimally active ones. Essential systems are equivalently defined as those square finite systems for which all nontrivial solutions are finite.
We prove that in every solvable twosided maxlinear system of minimally active or essential type, all positions in C := A ⊕ B active in any optimal permutation for the assignment problem for C, are also active for some nontrivial solution (any nontrivial solution in the minimally active case) of the twosided system. This enables us to deduce conditions on a solution x for which it is possible in some cases to find x in polynomial time. It is also proved that any essential system can be transformed to a minimally active system in polynomial time.
Original language  English 

Journal  Discrete Applied Mathematics 
Early online date  30 Jun 2018 
DOIs  
Publication status  Epub ahead of print  30 Jun 2018 
Keywords
 matrix
 Maxplus algebra
 twosided linear system
Fingerprint
Dive into the research topics of 'On twosided MaxLinear equations'. 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