On max-plus two-sided linear systems whose solution sets are min-plus linear
<|reference_start|>On max-plus two-sided linear systems whose solution sets are min-plus linear: 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.<|reference_end|>
@article{ooga2024on,
    title={On max-plus two-sided linear systems whose solution sets are min-plus
  linear},
    author={Yasutaka Ooga, Yuki Nishida, Yoshihide Watanabe},
    journal={arXiv preprint arXiv:2402.07358},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.07358},
    primaryClass={math.CO cs.NA math.NA}
}