Geodesic
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 
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/
@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},
     year = {2016},
     volume = {450},
     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
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
%U http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a3/
%G ru
%F ZNSL_2016_450_a3

Voir la notice du chapitre de livre 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.

[1] M. Akian, S. Gaubert, A. Guterman, “Tropical polyhedra are equivalent to mean payoff games”, Intern. J. Algebra Comput., 22:1 (2012), 1250001, 43 pp. | DOI | MR | Zbl

[2] P. Butcovič, “Strong regularity of matrices – a survey of results”, Discr. Appl. Math., 48 (1994), 45–68 | DOI | MR

[3] A. Davydow, New Algorithms for Solving Tropical Linear Systems, 2013, arXiv: 1309.5206

[4] D. Grigoriev, “Complexity of solving tropical linear systems”, Comput. Complexity, 22 (2013), 71–78 | DOI | MR

[5] Z. Izhakian, L. Rowen, “The tropical rank of a tropical matrix”, Commun. Algebra, 37:11 (2009), 3912–3927 | DOI | MR | Zbl

[6] Harold W. Kuhn, “The hungarian method for the assignment problem”, Naval Research Logistics Quarterly, 2 (1995), 83–97 | MR

[7] J. Richter-Gebert, B. Sturmfels, T. Theobald, “First steps in tropical geometry”, Idempotent Mathematics and Mathematical Physics, Contemp. Math., 377, 2005, 289–317 | DOI | MR | Zbl

[8] S. Reinhard, T. Thorsten, “Combinatorics and genus of tropical intersections and Ehrhart theory”, SIAM J. Discrete Math., 24:1 (2010), 17–32 | DOI | MR | Zbl

[9] L. Felipe Tabera et. al., “Tropical resultants for curves and stable intersection”, Revista Matemática Iberoamericana, 24:3 (2008), 941–961 | MR | Zbl

[10] Theobald Thorsten, “On the frontiers of polynomial computations in tropical geometry”, J. Symbolic Comput., 41:12 (2006), 1360–1375 | DOI | MR | Zbl