Projects per year
Abstract
This paper is a contribution to the study of finite, two-sided max-linear systems Ax = Bx over the max-plus algebra. These systems are known to be equivalent to mean-payoff games and the problem of deciding whether or not a non-trivial 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 non-trivial 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 non-trivial 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 non-trivial solutions are finite.
We prove that in every solvable two-sided max-linear 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 non-trivial solution (any non-trivial solution in the minimally active case) of the two-sided 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 non-trivial 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 non-trivial 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 non-trivial solutions are finite.
We prove that in every solvable two-sided max-linear 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 non-trivial solution (any non-trivial solution in the minimally active case) of the two-sided 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 | E-pub ahead of print - 30 Jun 2018 |
Keywords
- matrix
- Max-plus algebra
- two-sided linear system
Fingerprint
Dive into the research topics of 'On two-sided Max-Linear equations'. Together they form a unique fingerprint.Projects
- 1 Finished
-
Perron-Frobenius Theory and Max-Algebraic Combinatorics of Nonnegative Matrices
Butkovic, P. (Principal Investigator)
Engineering & Physical Science Research Council
12/03/12 → 11/03/14
Project: Research Councils