Geodesic
New algorithms for solving tropical linear systems
Algebra i analiz, Tome 28 (2016) no. 6, pp. 1-19.

Voir la notice de l'article provenant de la source Math-Net.Ru

The problem of solving tropical linear systems, a natural problem of tropical mathematics, has already proved to be very interesting from the algorithmic point of view: it is known to be in $NP\cap coNP$, but no polynomial time algorithm is known, although counterexamples for existing pseudopolynomial algorithms are (and must be) very complex. In this work, the study of algorithms for solving tropical linear systems is continued. First, a new reformulation of Grigoriev's algorithm is presented, which brings it closer to the algorithm of Akian, Gaubert, and Guterman; this makes it possible to formulate a whole family of new algorithms, and, for some algorithms in this family, none of the known superpolynomial counterexamples work. Second, a family of algorithms for solving overdetermined tropical systems is presented. Also, an explicit algorithm is exhibited that can solve a tropical linear system determined by an $(m\times n)$-matrix with maximal element $M$ in time $\Theta\left(\binom mn\mathrm{poly}\left(m,n,\log M\right)\right)$, and this time matches the complexity of the best of previously known algorithms for feasibility testing.
Keywords: tropical linear system, feasibility, Grigoriev's algorithm, Akian–Gaubert–Guterman algorithm. 
@article{AA_2016_28_6_a0,
     author = {A. Davydow},
     title = {New algorithms for solving tropical linear systems},
     journal = {Algebra i analiz},
     pages = {1--19},
     publisher = {mathdoc},
     volume = {28},
     number = {6},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/AA_2016_28_6_a0/}
}
TY  - JOUR
AU  - A. Davydow
TI  - New algorithms for solving tropical linear systems
JO  - Algebra i analiz
PY  - 2016
SP  - 1
EP  - 19
VL  - 28
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AA_2016_28_6_a0/
LA  - en
ID  - AA_2016_28_6_a0
ER  - 
%0 Journal Article
%A A. Davydow
%T New algorithms for solving tropical linear systems
%J Algebra i analiz
%D 2016
%P 1-19
%V 28
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AA_2016_28_6_a0/
%G en
%F AA_2016_28_6_a0
A. Davydow. New algorithms for solving tropical linear systems. Algebra i analiz, Tome 28 (2016) no. 6, pp. 1-19. http://geodesic.mathdoc.fr/item/AA_2016_28_6_a0/

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

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

[3] Bezem M., Nieuwenhuis R., Rodrígez-Carbonell E., “Hard problems in max-algebra, control theory, hypergraphs and other areas”, Inform. Process. Lett., 110:4 (2010), 133–138 | DOI | MR | Zbl

[4] Butkovič P., “Strong regularity of matrices – a survey of results”, Discrete Appl. Math., 48:1 (1994), 45–68 | DOI | MR | Zbl

[5] Cuninghame-Green R. A., Minimax algebra, Lecture Notes in Econom. and Math. Systems, 166, Springer-Verlag, Berlin, 1979 | DOI | MR | Zbl

[6] Davydov A. P., “Otsenki slozhnosti algoritma Grigoreva dlya resheniya tropicheskikh lineinykh sistem”, Zap. nauch. semin. POMI, 402, 2012, 69–82 | MR

[7] Develin M., Santos F., Sturmfels B., “On the rank of a tropical matrix”, Combinatorial and Computational Geometry, Math. Sci. Res. Inst. Publ., 52, Cambridge Univ. Press, Cambridge, 2005, 213–242 | MR | Zbl

[8] Ehrenfeucht A., Mycielski J., “Positional strategies for mean payoff games”, Internat. J. Game Theory, 8:2 (1979), 109–113 | DOI | MR | Zbl

[9] Floyd R. W., “Algorithm 97: shortest path”, Commun. ACM, 5:6 (1962), 345 | DOI

[10] Grigoriev D., Personal communication, 2013-09

[11] Grigoriev D., “Complexity of solving tropical linear systems”, Comput. Complexity, 22:1 (2013), 71–88 | DOI | MR | Zbl

[12] Grigoriev D., Podoltkii V. V., Complexity of tropical and min-plus linear prevarieties, 2012, arXiv: 1204.4578[cs.CC] | MR

[13] Izhakian Z., The tropical rank of a tropical matrix, 2008, arXiv: math/0604208v2[math.AC]

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

[15] Karp R. M., “A characterization of the minimum cycle mean in a digraph”, Discrete Math., 23:23 (1978), 309–311 | DOI | MR | Zbl

[16] Karzanov A. V., Gurvich V. A., Khachyan L. G., “Tsiklicheskie igry i nakhozhdenie minimaksnykh srednikh tsiklov v orientirovannykh grafakh”, Zh. vychisl. mat. i mat. fiz., 28:9 (1988), 1407–1417 | MR | Zbl

[17] Karzanov A. V., Lebedev V. N., “Cyclical games with prohibitions”, Math. Programming, 60:3 (1993), 277–293 | DOI | MR | Zbl

[18] Kleene S. C., “Representation of events in nerve nets and finite automata”, Automata Studies, Ann. Math. Stud., 34, Princeton Univ. Press, Princeton, NJ, 1956, 3–41 | MR

[19] Krivulin N. K., Metody idempotentnoi algebry v zadachakh modelirovaniya i analiza slozhnykh sistem, Izd-vo SPbGU, SPb., 2009

[20] Kuhn H. W., “The Hungarian method for the assignment problem”, Naval Res. Logist. Quart., 2 (1955), 83–97 | DOI | MR | Zbl

[21] Litvinov G. L., “Dekvantovanie Maslova idempotentnaya i tropicheskaya matematika: kratkoe vvedenie”, Zap. nauch. semin. POMI, 236, 2005, 145–182 ; arXiv: ; \ math/0507014 | MR | Zbl

[22] Litvinov G. L., Maslov V. P., Rodionov A. Ya., Sobolevski A. N., Universal algorithms, mathematics of semirings and parallel computations, Lecture Notes Comput. Sci. Eng., 75, Springer, Berlin, 2011 | MR

[23] Lozovanu D. D., “Algoritm resheniya nekotorykh klassov setevykh minimaksnykh zadach i ikh prilozheniya”, Diskret. mat., 6:2 (1994), 138–144 | MR | Zbl

[24] Lozovanu D. D., “Silnopolinomialnye algoritmy poiska minimaksnykh putei v setyakh i resheniya tsiklicheskikh igr”, Kibern. i sist. anal., 29:5 (1993), 754–759 | MR | Zbl

[25] Mikhalkin G., Enumerative tropical algebraic geometry in $\mathrm R^2$, ArXiv Mathematics e-prints, December 2003 | MR

[26] Noel V., Grigoriev D., Vakulenko S., Radulescu O., “Hybrid models of the cell cycle molecular machinery”, Electron. Proc. Theor. Comput. Sci., 92 (2012), 88–105 | DOI

[27] Noel V., Grigoriev D., Vakulenko S., Radulescu O., “Tropical geometries and dynamics of biochemical networks”, Application to hybrid cell cycle models, Electron. Notes Theor. Comput. Sci., 284, Elsevier Sci. B. V., Amsterdam, 2012, 75–91 | DOI | MR | Zbl

[28] Pin J.-E., “Positive varieties and infinite words”, Lecture Notes in Comput. Sci., 1380, Springer, Berlin, 1998, 76–87 ; http://dblp.uni-trier.de | DOI | MR | Zbl

[29] Richter-Gebert J., Sturmfels B., Theobald T., First steps in tropical geometry, ArXiv Mathematics e-prints, arXiv: ; June 2003 math/0306366 | MR

[30] Simon I., “Recognizable sets with multiplicities in the tropical semiring”, Mathematical Foundations of Computer Science, Lecture Notes in Comput. Sci., 324, Springer, Berlin, 107–120 | DOI | MR

[31] Speyer D., Sturmfels B., Tropical mathematics, ArXiv Mathematics e-prints, August 2004, arXiv: math/0408099 | MR

[32] Zwick U., Paterson M., “The complexity of mean payoff games on graphs”, Theoret. Comput. Sci., 158:1–2 (1996), 342–359 | MR