Polynomial and Pseudopolynomial Procedures for Solving Interval Two-Sided (Max, Plus)-Linear Systems
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 pseudopolynom...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-11-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/9/22/2951 |
| _version_ | 1797509440839090176 |
|---|---|
| author | Helena Myšková Ján Plavka |
| author_facet | Helena Myšková Ján Plavka |
| author_sort | Helena Myšková |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-10T05:18:43Z |
| format | Article |
| id | doaj.art-598910d008374fdaa7c7e8d03f0ac760 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T05:18:43Z |
| publishDate | 2021-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-598910d008374fdaa7c7e8d03f0ac7602023-11-23T00:15:34ZengMDPI AGMathematics2227-73902021-11-01922295110.3390/math9222951Polynomial and Pseudopolynomial Procedures for Solving Interval Two-Sided (Max, Plus)-Linear SystemsHelena Myšková0Ján Plavka1Department of Mathematics and Theoretical Informatics, Technical University of Košice, 04200 Košice, SlovakiaDepartment of Mathematics and Theoretical Informatics, Technical University of Košice, 04200 Košice, SlovakiaMax-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.https://www.mdpi.com/2227-7390/9/22/2951interval solutionsolvabilitymax-plus matrix |
| spellingShingle | Helena Myšková Ján Plavka Polynomial and Pseudopolynomial Procedures for Solving Interval Two-Sided (Max, Plus)-Linear Systems Mathematics interval solution solvability max-plus matrix |
| title | Polynomial and Pseudopolynomial Procedures for Solving Interval Two-Sided (Max, Plus)-Linear Systems |
| title_full | Polynomial and Pseudopolynomial Procedures for Solving Interval Two-Sided (Max, Plus)-Linear Systems |
| title_fullStr | Polynomial and Pseudopolynomial Procedures for Solving Interval Two-Sided (Max, Plus)-Linear Systems |
| title_full_unstemmed | Polynomial and Pseudopolynomial Procedures for Solving Interval Two-Sided (Max, Plus)-Linear Systems |
| title_short | Polynomial and Pseudopolynomial Procedures for Solving Interval Two-Sided (Max, Plus)-Linear Systems |
| title_sort | polynomial and pseudopolynomial procedures for solving interval two sided max plus linear systems |
| topic | interval solution solvability max-plus matrix |
| url | https://www.mdpi.com/2227-7390/9/22/2951 |
| work_keys_str_mv | AT helenamyskova polynomialandpseudopolynomialproceduresforsolvingintervaltwosidedmaxpluslinearsystems AT janplavka polynomialandpseudopolynomialproceduresforsolvingintervaltwosidedmaxpluslinearsystems |