The complexity of tropical matrix factorization

• Autores: Yaroslav Shitov
• Localización: Advances in mathematics, ISSN 0001-8708, Vol. 254, Nº 1, 2014, págs. 138-156
• Idioma: inglés
• DOI: 10.1016/j.aim.2013.12.013
• Texto completo no disponible (Saber más ...)
• Referencias bibliográficas
  • M. Akian, S. Gaubert, A. Guterman, Linear independence over tropical semirings and beyond, in: Contemp. Math., vol. 495, Amer. Math. Soc.,...
  • F. Baccelli, G. Cohen, G.J. Olsder, J.P. Quadrat, Synchronization and Linearity, Wiley, 1992.
  • A.I. Barvinok, Combinatorial optimization and computations in the ring of polynomials, DIMACS Technical Report 93-13, 1993.
  • A.I. Barvinok, Two algorithmic results for the traveling salesman problem, Math. Oper. Res. 21 (1) (1996) 65–84.
  • A. Barvinok, D.S. Johnson, G.J. Woeginger, R. Woodroofe, The maximum traveling salesman problem under polyhedral norms, in: Integer Programming...
  • A. Barvinok, E.Kh. Gimadi, A.I. Serdyukov, The maximum traveling salesman problem, in: G. Gutin, A. Punnen (Eds.), The Traveling Salesman...
  • L.B. Beasley, Isolation number versus Boolean rank, Linear Algebra Appl. 436 (2012) 3469–3474.
  • L.B. Beasley, N.J. Pullman, Semiring rank versus column rank, Linear Algebra Appl. 101 (1988) 33–48.
  • L.B. Beasley, S.J. Kirkland, B.L. Shader, Rank comparisons, Linear Algebra Appl. 221 (1995) 171–188.
  • E. Cela, R. Rudolf, G. Woeginger, On the Barvinok rank of matrices, Presentation at the 2nd Aussois Workshop on Combinatorial Optimization,...
  • J.E. Cohen, U.G. Rothblum, Nonnegative ranks, decompositions, and factorizations of nonnegative matrices, Linear Algebra Appl. 190 (1993)...
  • R.A. Cuninghame-Green, Minimax Algebra, Lecture Notes in Econom. and Math. Systems, vol. 166, Springer-Verlag, Berlin, 1979.
  • M. Develin, The moduli space of n tropically collinear points in Rd, Collect. Math. 56 (1) (2005) 1–19.
  • M. Develin, Tropical secant varieties of linear spaces, Discrete Comput. Geom. 35 (1) (2006) 117–129.
  • M. Develin, F. Santos, B. Sturmfels, On the rank of a tropical matrix, in: E. Goodman, J. Pach, E. Welzl (Eds.), Discrete and Computational...
  • M. Einsiedler, M. Kapranov, D. Lind, Non-archimedean amoebas and tropical varieties, J. Reine Angew. Math. 601 (2006) 139–157.
  • J. Ferrante, C. Rackoff, A decision procedure for the first order theory of real addition with order, SIAM J. Comput. 4 (1975) 69–76.
  • M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness, W. H. Freeman and Company, San Francisco,...
  • S. Gaubert, On the Burnside problem for semigroups of matrices in the (max,+) algebra, Semigroup Forum 52 (1996) 271–292.
  • S. Gaubert, M. Plus, Methods and Applications of (max,+) Linear Algebra, Lecture Notes in Comput. Sci., vol. 1200, Springer-Verlag, New...
  • D.A. Gregory, N.J. Pullman, Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices, J. Combin. Theory Ser....
  • A.E. Guterman, Ya.N. Shitov, Tropical patterns of matrices and the Gondran–Minoux rank function, Linear Algebra Appl. 437 (7) (2012) 1793–1811.
  • B. Heidergott, G.J. Olsder, J. van der Woude, Max Plus at Work: Modeling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra...
  • A. Hultman, J. Jonsson, The topology of the space of matrices of Barvinok rank two, arXiv: 0902.3380v1.
  • Z. Izhakian, M. Johnson, M. Kambites, Tropical matrix groups, arXiv:1203.2449.
  • M. Johnson, M. Kambites, Multiplicative structure of 2×2 tropical matrices, Linear Algebra Appl. 435 (2011) 1612–1625.
  • V.N. Kolokoltsov, V.P. Maslov, Idempotent Analysis and Applications, Kluwer Acad. Publishers, 1997.
  • W.M. McEneaney, Max-Plus Methods for Nonlinear Control and Estimation, Systems Control Found. Appl., Birkhäuser Boston, Inc., Boston, MA,...
  • J.-E. Pin, Tropical semirings, in: Idempotency, Bristol, 1994, in: Publ. Newton Inst., vol. 11, Cambridge Univ. Press, Cambridge, 1998.
  • I. Simon, Limited subsets of a free monoid, in: Proc. 19th Annual Symposium on Foundations of Computer Science, Institute of Electrical and...
  • N.N. Vorobyev, Extremal algebra of positive matrices, Elektron. Inf.verarb. Kybern. 3 (1967) 39–71.