Polynomial and Pseudopolynomial Procedures for Solving Interval Two-Sided (Max, Plus)-Linear Systems

Helena Myšková and Ján Plavka
Additional contact information
Helena Myšková: Department of Mathematics and Theoretical Informatics, Technical University of Košice, 04200 Košice, Slovakia
Ján Plavka: Department of Mathematics and Theoretical Informatics, Technical University of Košice, 04200 Košice, Slovakia

Mathematics, 2021, vol. 9, issue 22, 1-13

Abstract: Max-plus algebra is the similarity of the classical linear algebra with two binary operations, maximum and addition. The notation Ax = Bx, where A, B are given (interval) matrices, represents (interval) two-sided (max, plus)-linear system. For the solvability of Ax = Bx, there are some pseudopolynomial algorithms, but a polynomial algorithm is still waiting for an appearance. The paper deals with the analysis of solvability of two-sided (max, plus)-linear equations with inexact (interval) data. The purpose of the paper is to get efficient necessary and sufficient conditions for solvability of the interval systems using the property of the solution set of the non-interval system Ax = Bx. The main contribution of the paper is a transformation of weak versions of solvability to either subeigenvector problems or to non-interval two-sided (max, plus)-linear systems and obtaining the equivalent polynomially checked conditions for the strong versions of solvability.

Keywords: interval solution; solvability; max-plus matrix (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/22/2951/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/22/2951/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:22:p:2951-:d:682588

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().