New algorithms for solving tropical linear systems

Davydow, A.

doi:10.1090/spmj/1470

New algorithms for solving tropical linear systems
HTML articles powered by AMS MathViewer

by A. Davydow

St. Petersburg Math. J. 28 (2017), 727-740

DOI: https://doi.org/10.1090/spmj/1470

Published electronically: October 2, 2017

PDF | Request permission

Abstract:

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.

An explicit algorithm is exhibited in the paper that can solve a tropical linear system determined by an $(m\times n)$-matrix with maximal element $M$ in time $\Theta \big (\binom {m}{n}\mathrm {poly} \big (m, n, \log M\big )\big )$, and this time matches the complexity of the best of previously known algorithms for feasibility testing.

References

M. Akian, S. Gaubert, and A. Guterman, The correspondence between tropical convexity and mean payoff games, Proc. 19 Internat. Symp. Math. Theory of Networks and Systems, Budapest, 2010, pp. 1295–1302.
Marianne Akian, Stéphane Gaubert, and Alexander Guterman, Tropical polyhedra are equivalent to mean payoff games, Internat. J. Algebra Comput. 22 (2012), no. 1, 1250001, 43. MR 2900854, DOI 10.1142/S0218196711006674
Marc Bezem, Robert Nieuwenhuis, and Enric Rodríguez-Carbonell, Hard problems in max-algebra, control theory, hypergraphs and other areas, Inform. Process. Lett. 110 (2010), no. 4, 133–138. MR 2584081, DOI 10.1016/j.ipl.2009.11.007
Peter Butkovič, Strong regularity of matrices—a survey of results, Discrete Appl. Math. 48 (1994), no. 1, 45–68. MR 1254755, DOI 10.1016/0166-218X(92)00104-T
Raymond Cuninghame-Green, Minimax algebra, Lecture Notes in Economics and Mathematical Systems, vol. 166, Springer-Verlag, Berlin-New York, 1979. MR 580321
A. P. Davydov, Bounds for the complexity of Grigoriev’s algorithm for solving tropical linear systems, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 402 (2012), no. Kombinatorika i Teoriya Grafov. IV, 69–82, 219 (Russian, with English and Russian summaries); English transl., J. Math. Sci. (N.Y.) 192 (2013), no. 3, 295–302. MR 2981979, DOI 10.1007/s10958-013-1395-5
Mike Develin, Francisco Santos, and Bernd Sturmfels, On the rank of a tropical matrix, Combinatorial and computational geometry, Math. Sci. Res. Inst. Publ., vol. 52, Cambridge Univ. Press, Cambridge, 2005, pp. 213–242. MR 2178322
A. Ehrenfeucht and J. Mycielski, Positional strategies for mean payoff games, Internat. J. Game Theory 8 (1979), no. 2, 109–113. MR 550954, DOI 10.1007/BF01768705
R. W. Floyd, Algorithm 97: shortest path., Commun. ACM 5 (1962), no. 6, 345; http:// doi.acm.org/10.1145/367766.368168.
D. Grigoriev, Personal communication, 2013-09.
Dima Grigoriev, Complexity of solving tropical linear systems, Comput. Complexity 22 (2013), no. 1, 71–88. MR 3034020, DOI 10.1007/s00037-012-0053-5
D. Grigoriev and V. V. Podolskii, Complexity of tropical and min-plus linear prevarieties, CoRR, abs/1204.4578, 2012.
Zur Izhakian, Tropical arithmetic and matrix algebra, Comm. Algebra 37 (2009), no. 4, 1445–1468. MR 2510993, DOI 10.1080/00927870802466967
Zur Izhakian and Louis Rowen, The tropical rank of a tropical matrix, Comm. Algebra 37 (2009), no. 11, 3912–3927. MR 2573227, DOI 10.1080/00927870902828793
Richard M. Karp, A characterization of the minimum cycle mean in a digraph, Discrete Math. 23 (1978), no. 3, 309–311. MR 523080, DOI 10.1016/0012-365X(78)90011-0
V. A. Gurvich, A. V. Karzanov, and L. G. Khachiyan, Cyclic games and finding minimax mean cycles in digraphs, Zh. Vychisl. Mat. i Mat. Fiz. 28 (1988), no. 9, 1407–1417, 1439 (Russian); English transl., U.S.S.R. Comput. Math. and Math. Phys. 28 (1988), no. 5, 85–91 (1990). MR 967535, DOI 10.1016/0041-5553(88)90012-2
Alexander V. Karzanov and Vasilij N. Lebedev, Cyclical games with prohibitions, Math. Programming 60 (1993), no. 3, Ser. A, 277–293. MR 1234877, DOI 10.1007/BF01580616
S. C. Kleene, Representation of events in nerve nets and finite automata, Automata studies, Annals of Mathematics Studies, no. 34, Princeton University Press, Princeton, N.J., 1956, pp. 3–41. MR 0077478
N. K. Krivulin, Idempotent algebra methods for problems in modelling and analysis of complex systems, St. Petersburg. Univ., St. Petersburg, 2009. (Russian)
H. W. Kuhn, The Hungarian method for the assignment problem, Naval Res. Logist. Quart. 2 (1955), 83–97. MR 75510, DOI 10.1002/nav.3800020109
G. L. Litvinov, The Maslov dequantization, and idempotent and tropical mathematics: a brief introduction, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 326 (2005), no. Teor. Predst. Din. Sist. Komb. i Algoritm. Metody. 13, 145–182, 282 (Russian, with English and Russian summaries); English transl., J. Math. Sci. (N.Y.) 140 (2007), no. 3, 426–444. MR 2183219, DOI 10.1007/s10958-007-0450-5
Grigory L. Litvinov, Victor P. Maslov, Anatoly Ya. Rodionov, and Andrei N. Sobolevski, Universal algorithms, mathematics of semirings and parallel computations, Coping with complexity: model reduction and data analysis, Lect. Notes Comput. Sci. Eng., vol. 75, Springer, Berlin, 2011, pp. 63–89. MR 2757572, DOI 10.1007/978-3-642-14941-2_{4}
D. D. Lozovanu and V. A. Trubin, The problem of the minimax path in a network and an algorithm for its solution, Diskret. Mat. 6 (1994), no. 2, 138–144 (Russian, with Russian summary); English transl., Discrete Math. Appl. 4 (1994), no. 5, 447–453. MR 1290413, DOI 10.1515/dma.1994.4.5.447
D. D. Lozovanu, Strongly polynomial algorithms for the search for minimax paths in networks and for the solution of cyclic games, Kibernet. Sistem. Anal. 5 (1993), 145–151, 190 (Russian, with English and Ukrainian summaries); English transl., Cybernet. Systems Anal. 29 (1993), no. 5, 754–759 (1994). MR 1300561, DOI 10.1007/BF01125805
Grigory Mikhalkin, Enumerative tropical algebraic geometry in $\Bbb R^2$, J. Amer. Math. Soc. 18 (2005), no. 2, 313–377. MR 2137980, DOI 10.1090/S0894-0347-05-00477-7
V. Noel, D. Grigoriev, S. Vakulenko, and O. Radulescu, Hybrid models of the cell cycle molecular machinery, Electron. Proc. Theor. Comput. Sci. 92 (2012), 88–105.
Vincent Noel, Dima Grigoriev, Sergei Vakulenko, and Ovidiu Radulescu, Tropical geometries and dynamics of biochemical networks application to hybrid cell cycle models, Proceedings of the 2nd International Workshop on Static Analysis and Systems Biology (SASB 2011), Electron. Notes Theor. Comput. Sci., vol. 284, Elsevier Sci. B. V., Amsterdam, 2012, pp. 75–91. MR 2956838, DOI 10.1016/j.entcs.2012.05.016
Jean-Éric Pin, Positive varieties and infinite words, LATIN’98: theoretical informatics (Campinas, 1998) Lecture Notes in Comput. Sci., vol. 1380, Springer, Berlin, 1998, pp. 76–87. MR 1635489, DOI 10.1007/BFb0054312
Jürgen Richter-Gebert, Bernd Sturmfels, and Thorsten Theobald, First steps in tropical geometry, Idempotent mathematics and mathematical physics, Contemp. Math., vol. 377, Amer. Math. Soc., Providence, RI, 2005, pp. 289–317. MR 2149011, DOI 10.1090/conm/377/06998
Imre Simon, Recognizable sets with multiplicities in the tropical semiring, Mathematical foundations of computer science, 1988 (Carlsbad, 1988) Lecture Notes in Comput. Sci., vol. 324, Springer, Berlin, 1988, pp. 107–120. MR 1023416, DOI 10.1007/BFb0017135
David Speyer and Bernd Sturmfels, Tropical mathematics, Math. Mag. 82 (2009), no. 3, 163–173. MR 2522909, DOI 10.1080/0025570x.2009.11953615
Uri Zwick and Mike Paterson, The complexity of mean payoff games on graphs, Theoret. Comput. Sci. 158 (1996), no. 1-2, 343–359. MR 1388974, DOI 10.1016/0304-3975(95)00188-3