The complexity of tropical matrix factorization

Abstract

The tropical arithmetic operations on $\mathbb{R}$ are defined by $a\oplus b=\min \{a,b\}$ and $a\otimes b=a+b$. Let $A$ be a tropical matrix and $k$ a positive integer, the problem of Tropical Matrix Factorization (TMF) asks whether there exist tropical matrices $B\in {\mathbb{R}}^{m\times k}$ and $C\in {\mathbb{R}}^{k\times n}$ satisfying $B\otimes C=A$. We show that no algorithm for TMF is likely to work in polynomial time for every fixed $k$, thus resolving a problem proposed by Barvinok in 1993.

16 pages, revised version

Cited by in corpus (1)

• Idempotent and tropical mathematics. Complexity of algorithms and interval analysis