An Algorithm for Solving an Overdetermined Tropical Linear System Using the Analysis of Stable Solutions of Subsystems

Abstract

In this paper, we show that an overdetermined tropical linear system has a solution if and only if it contains a square subsystem having a stable solution that is a solution of the original system. This leads to a simple algorithm for solving tropical linear systems in time \( O\left(\left({}_n^m\right)\right){n}^4 \), where m is the number of equations and n is the number of variables. For weakly overdetermined systems, this time is polynomial.