  Matrix factorization problems over various semirings naturally arise in
different contexts of modern pure and applied mathematics. These problems are
very hard in general and cause computational difficulties in applications. We
give a survey of what is known on the algorithmic complexity of Boolean, fuzzy,
tropical, nonnegative, and positive semidefinite factorizations, and we examine
the behavior of the corresponding rank functions on matrices of bounded
bandwidth. We show that the Boolean, fuzzy, and tropical versions of matrix
factorization become polynomial time solvable when restricted to this class of
matrices, and we also show that the nonnegative rank of a tridiagonal matrix is
easy to compute. We recall several open problems from earlier papers on the
topic and formulate many new problems.

Combinatorics