Email this article An Algorithm for Solving an Overdetermined Tropical Linear System Using the Analysis of Stable Solutions of Subsystems
- Authors: Davydow A.1
-
Affiliations:
- St. Petersburg Academic University
- Issue: Vol 232, No 1 (2018)
- Pages: 25-35
- Section: Article
- URL: https://journals.rcsi.science/1072-3374/article/view/241255
- DOI: https://doi.org/10.1007/s10958-018-3856-3
- ID: 241255
Cite item
Open Access
Access granted
Subscription Access
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.
About the authors
A. Davydow
St. Petersburg Academic University
Author for correspondence.
Email: adavydow@gmail.com
Russian Federation, St. Petersburg
Supplementary files
