E-viri
Recenzirano
Odprti dostop
-
Ooga, Yasutaka; Nishida, Yuki; Watanabe, Yoshihide
Linear algebra and its applications, 08/2024, Letnik: 694Journal Article
The max-plus algebra R∪{−∞} is defined in terms of a combination of the following two operations: addition a⊕b:=max(a,b) and multiplication a⊗b:=a+b. In this study, we propose a new method to characterize the set of all solutions of a max-plus two-sided linear system A⊗x=B⊗x. We demonstrate that the minimum “min-plus” linear subspace containing the “max-plus” solution space can be computed by applying the alternating method, which is a well-known algorithm to compute single solutions of two-sided systems. Further, we derive a sufficient condition for the “min-plus” and “max-plus” subspaces to be identical. The computational complexity of the algorithm presented in this study is pseudo-polynomial.
