Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.07358 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908603829452800 |
|---|---|
| author | Ooga, Yasutaka Nishida, Yuki Watanabe, Yoshihide |
| author_facet | Ooga, Yasutaka Nishida, Yuki Watanabe, Yoshihide |
| contents | The max-plus algebra $\mathbb{R}\cup \{-\infty \}$ is defined in terms of a combination of the following two operations: addition, $a \oplus b := \max(a,b)$, and multiplication, $a \otimes 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 \otimes x = B \otimes x$. We demonstrate that the minimum ``min-plus'' linear subspace containing the ``max-plus'' solution space can be computed by applying the alternating method algorithm, which is a well-known method 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 method presented in this study is pseudo-polynomial. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_07358 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On max-plus two-sided linear systems whose solution sets are min-plus linear Ooga, Yasutaka Nishida, Yuki Watanabe, Yoshihide Combinatorics Numerical Analysis 15A80, 15A06, 15A39 The max-plus algebra $\mathbb{R}\cup \{-\infty \}$ is defined in terms of a combination of the following two operations: addition, $a \oplus b := \max(a,b)$, and multiplication, $a \otimes 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 \otimes x = B \otimes x$. We demonstrate that the minimum ``min-plus'' linear subspace containing the ``max-plus'' solution space can be computed by applying the alternating method algorithm, which is a well-known method 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 method presented in this study is pseudo-polynomial. |
| title | On max-plus two-sided linear systems whose solution sets are min-plus linear |
| topic | Combinatorics Numerical Analysis 15A80, 15A06, 15A39 |
| url | https://arxiv.org/abs/2402.07358 |