The complexity of tropical matrix factorization

DOI10.1016/j.aim.2013.12.013zbMath1359.68112arXiv1205.7079OpenAlexW1998867519MaRDI QIDQ2445938

Yaroslav N. Shitov

Publication date: 15 April 2014

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1205.7079

zbMATH Keywords

complexity theorymatrix factorizationtropical semiring

Mathematics Subject Classification ID

Factorization of matrices (15A23) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Max-plus and related algebras (15A80)

Related Items

Rank functions of tropical matrices ⋮ Idempotent and tropical mathematics; complexity of algorithms and interval analysis ⋮ Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks ⋮ Algorithms for approximate subtropical matrix factorization ⋮ Detecting matrices of combinatorial rank three ⋮ Factoring a band matrix over a semiring ⋮ Tropical lower bounds for extended formulations ⋮ Tropical representations and identities of plactic monoids ⋮ Tropical lower bound for extended formulations. II. Deficiency graphs of matrices ⋮ Tropical semimodules of dimension two

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Isolation number versus Boolean rank
• Tropical patterns of matrices and the Gondran-Minoux rank function
• Multiplicative structure of \(2\times 2\) tropical matrices
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices
• Tropical secant varieties of linear spaces
• Max-plus methods for nonlinear control and estimation.
• The topology of the space of matrices of Barvinok rank two
• Semiring rank versus column rank
• Tropical matrix groups
• The moduli space of \(n\) tropically collinear points in \(\mathbb R^d\)
• Rank comparisons
• On the Burnside problem for semigroups of matrices in the \((\max,+)\) algebra
• Linear independence over tropical semirings and beyond
• Non-archimedean amoebas and tropical varieties
• A Decision Procedure for the First Order Theory of Real Addition with Order
• Two Algorithmic Results for the Traveling Salesman Problem
• Methods and applications of (max,+) linear algebra