Geodesic
Upper and lower bounds for Grigoriev's algorithm for solving integral tropical linear systems
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IV, Tome 402 (2012), pp. 69-82 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We investigate an algorithm for solving integral tropical linear systems proposed by D. Yu. Grigoriev in 2010, We give the first nonpolynominal lower bound on time complexity of the algorithm, and also improve known upper bound. 
@article{ZNSL_2012_402_a4,
     author = {A. P. Davydow},
     title = {Upper and lower bounds for {Grigoriev's} algorithm for solving integral tropical linear systems},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {69--82},
     year = {2012},
     volume = {402},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a4/}
}
TY  - JOUR
AU  - A. P. Davydow
TI  - Upper and lower bounds for Grigoriev's algorithm for solving integral tropical linear systems
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2012
SP  - 69
EP  - 82
VL  - 402
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a4/
LA  - ru
ID  - ZNSL_2012_402_a4
ER  - 
%0 Journal Article
%A A. P. Davydow
%T Upper and lower bounds for Grigoriev's algorithm for solving integral tropical linear systems
%J Zapiski Nauchnykh Seminarov POMI
%D 2012
%P 69-82
%V 402
%U http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a4/
%G ru
%F ZNSL_2012_402_a4
A. P. Davydow. Upper and lower bounds for Grigoriev's algorithm for solving integral tropical linear systems. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IV, Tome 402 (2012), pp. 69-82. http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a4/

[1] M. Akian, S. Gaubert, A. Guterman, “The correspondence between tropical convexity and mean payoff games”, Proceedings of the 19th Intern. Symp. Math. Theory of Networks and Systems, Budapest, 2010, 1295–1302 | MR

[2] P. Butkovic, F. Hevery, “A condition for the strong regularity of matrices in the minimax algebra”, Discr. Appl. Math., 11 (1985), 209–222 | DOI | MR | Zbl

[3] Dima Grigoriev, Complexity of solving tropical linear systems, Preprint MPIM 2010-60, Bonn | MR

[4] Dima Grigoriev, Vladimir Shpilrain, Tropical cryptography, Preprint MPIM 2011-11, Bonn | MR

[5] B. Huber, B. Sturmfels, “A polyhedral method for solving sparse polynomial systems”, Math. of Computation, 64 (1995), 1541–1555 | DOI | MR | Zbl

[6] V. Podolskii, Lichnoe soobschenie