An algorithm for solving an overdetermined tropical linear system with the help of analysis of stable solutions of subsystems
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VIII, Tome 450 (2016), pp. 43-61
Voir la notice de l'article provenant de la source Math-Net.Ru
In this paper we show that an overdetermined tropical linear system has a solution if and only if it contains a square subsystem with a stable solution which is a solution of the initial system. This leads us to a simple algorithm solving tropical linear systems in $O(C_m^nn^4)$ time, where $m$ is a number of equations and $n$ is a number of variables. In the particular case of weekly overdetermined systems this time is polynomial.
@article{ZNSL_2016_450_a3,
author = {A. Davydow},
title = {An algorithm for solving an overdetermined tropical linear system with the help of analysis of stable solutions of subsystems},
journal = {Zapiski Nauchnykh Seminarov POMI},
pages = {43--61},
publisher = {mathdoc},
volume = {450},
year = {2016},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a3/}
}
TY - JOUR AU - A. Davydow TI - An algorithm for solving an overdetermined tropical linear system with the help of analysis of stable solutions of subsystems JO - Zapiski Nauchnykh Seminarov POMI PY - 2016 SP - 43 EP - 61 VL - 450 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a3/ LA - ru ID - ZNSL_2016_450_a3 ER -
%0 Journal Article %A A. Davydow %T An algorithm for solving an overdetermined tropical linear system with the help of analysis of stable solutions of subsystems %J Zapiski Nauchnykh Seminarov POMI %D 2016 %P 43-61 %V 450 %I mathdoc %U http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a3/ %G ru %F ZNSL_2016_450_a3
A. Davydow. An algorithm for solving an overdetermined tropical linear system with the help of analysis of stable solutions of subsystems. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VIII, Tome 450 (2016), pp. 43-61. http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a3/