The weak robustness of interval matrices in max-plus algebra. (English) Zbl 1311.15028
Summary: A max-plus matrix \(A\) (operations \(\max\) and plus are denoted by \(\oplus\) and \(\otimes\), respectively) is called weakly robust if the only possibility to arrive at an eigenvector is to start the sequence (orbit) \(x, A \otimes x, A^2 \otimes x, \dots\) by a vector that is itself an eigenvector. The weak robustness of a matrix is extended to interval max-plus matrices distinguishing two possibilities, that at least one matrix or all matrices from a given interval are weakly robust. Weakly robust interval matrices in max-plus algebra are studied and equivalent conditions for interval matrices to be weakly robust are presented. The recognition version of the problem of the existence of at least one weakly robust matrix from a given interval is proved to be NP-complete.
References:
| [1] | Butkovič, P., (Max-linear Systems: Theory and Algorithms. Max-linear Systems: Theory and Algorithms, Springer Monographs in Mathematics (2010), Springer-Verlag) · Zbl 1202.15032 |
| [2] | Butkovič, P.; Schneider, H.; Sergeev, S., Recognizing weakly stable matrices, SIAM J. Control Optim., 50, 5, 3029-3051 (2012) · Zbl 1267.15024 |
| [3] | Cuninghame-Green, R. A., Describing industrial processes with interference and approximating their steady-state behaviour, Oper. Res. Quart., 13, 95-100 (1962) |
| [4] | Cuninghame-Green, R. A., Minimax algebra and applications, Adv. Imag. Electron Phys., 90, 1-121 (1995) |
| [5] | Cuninghame-Green, R. A., (Minimax Algebra. Minimax Algebra, Lecture Notes in Economics and Mathematical Systems, vol. 166 (1979), Springer: Springer Berlin) · Zbl 0498.90084 |
| [6] | Gavalec, M., Linear matrix period in max-plus algebra, Linear Algebra Appl., 307, 167-182 (2000) · Zbl 0998.15020 |
| [7] | Gavalec, M.; Zimmermann, K., Classification of solutions to systems of two-sided equations with interval coefficients, Int. J. Pure Appl. Math., 45, 533-542 (2008) · Zbl 1154.65036 |
| [8] | Karp, R. M., A characterization of the minimum cycle mean in a digraph, Discrete Math., 23, 309-311 (1978) · Zbl 0386.05032 |
| [9] | Lacko, V.; Berežný, Š., The color-balanced spanning tree problem, Kybernetika, 41, 539-546 (2005) · Zbl 1249.05053 |
| [10] | Lawler, E. L., Combinatorial Optimization: Networks and Matroids (1976), Holt, Rinehart and Wilston: Holt, Rinehart and Wilston New York · Zbl 0413.90040 |
| [11] | Molnárová, M.; Pribiš, J., Matrix period in max-algebra, Discrete Appl. Math., 103, 167-175 (2000) · Zbl 0952.05043 |
| [12] | Myšková, H., Control solvability of interval systems of max-separable linear equations, Linear Algebra Appl., 416, 215-223 (2006) · Zbl 1129.15003 |
| [13] | Myšková, H., Interval systems of max-separable linear equations, Linear Algebra and its Applications, 403, 263-272 (2005) · Zbl 1077.15004 |
| [14] | Myšková, M., Max-\( \min\) interval systems of linear equations with bounded solution, Kybernetika, 48, 2, 299-308 (2012) · Zbl 1272.15002 |
| [15] | Papadimitriou, Ch. H.; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity (1882), Prentice-Hall, Inc.: Prentice-Hall, Inc. New Jersey |
| [16] | Plavka, J., On the \(O(n^3)\) algorithm for checking the strong robustness of interval fuzzy matrices, Discrete Appl. Math., 160, 640-647 (2012) · Zbl 1251.65065 |
| [17] | Plavka, J., The complexity of finding the minimal of the maximum cycle means of similar zero-one matrices, Optimization, 283-287 (1994) · Zbl 0815.68080 |
| [18] | Plavka, J.; Szabó, P., On the \(\lambda \)-robustness of matrices over fuzzy algebra, Discrete Appl. Math., 159, 5, 381-388 (2011) · Zbl 1225.15027 |
| [19] | Rohn, J., Systems of linear interval equations, Linear Algebra and its Applications, 126, 39-78 (1989) · Zbl 0712.65029 |
| [20] | Sergeev, S., Max-algebraic cones of nonnegative irreducible matrices, Linear Algebra and its Applications, 435, 1736-1757 (2011) · Zbl 1226.15017 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
