On two-sided Max-Linear equations

Research output: Contribution to journalArticlepeer-review

Standard

On two-sided Max-Linear equations. / Jones, Daniel.

In: Discrete Applied Mathematics, 30.06.2018.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

Bibtex

@article{461abbd0145741eb80dfcf22dc54a507,
title = "On two-sided Max-Linear equations",
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 reducedto 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.",
keywords = "matrix, Max-plus algebra, two-sided linear system",
author = "Daniel Jones",
year = "2018",
month = jun,
day = "30",
doi = "10.1016/j.dam.2018.06.011",
language = "English",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - On two-sided Max-Linear equations

AU - Jones, Daniel

PY - 2018/6/30

Y1 - 2018/6/30

N2 - 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 reducedto 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.

AB - 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 reducedto 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.

KW - matrix

KW - Max-plus algebra

KW - two-sided linear system

U2 - 10.1016/j.dam.2018.06.011

DO - 10.1016/j.dam.2018.06.011

M3 - Article

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -