The nonnegative rank of a matrix: Hard problems, easy solutions

R. Karp, Reducibility Among Combinatorial Problems, Proceedings of the Symposium on the Complexity of Computer Computations (1972) 85–103

1972

Earlier work this paper cites.

L. B. Thomas, Rank Factorization of Nonnegative Matrices, SIAM Review

1973

Earlier work this paper cites.

J. Orlin, Contentment in graph theory: Covering graphs with cliques, Indagationes Mathematicae

1977

Earlier work this paper cites.

D. de Caen, D. A. Gregory, N. J. Pullman, The Boolean rank of zero-one matrices. In Proceedings of the Third Caribbean Conference on Combinatorics and Computing (Bridgetown, 1981)

1981

Earlier work this paper cites.

D. A. Gregory, N. J. Pullman, K. F. Jones, J. R. Lundgren, Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices, Journal of Combinatorial Theory, Series B

1991

Earlier work this paper cites.

M. Yannakakis, Expressing combinatorial optimization problems by linear programs, Journal of Computer and System Sciences

1991

Earlier work this paper cites.

J. E. Cohen, U. G. Rothblum, Nonnegative ranks, decompositions, and factorizations of nonnegative matrices, Linear Algebra and Its Applications

1993

Earlier work this paper cites.

T. Jiang, B. Ravikumar, Minimal NFA problems are hard, SIAM Journal on Computing

1993

Earlier work this paper cites.

D. D. Lee, H. S. Seung, Learning the parts of objects by non-negative matrix factorization, Nature

1999

Cited alongside, same era.

M. C. Golumbic, T. Hirst M. Lewenstein, Uniquely restricted matchings, Algorithmica

2001

Cited alongside, same era.

S. Vavasis, On the complexity of nonnegative matrix factorization, SIAM Journal on Optimization

2009

Cited alongside, same era.

M. Conforti, G. Cornuéjols, G. Zambelli, Extended formulations in combinatorial optimization, 4OR

2010

Cited alongside, same era.

S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, R. de Wolf, Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds, in Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing,

2012

Cited alongside, same era.

P. Chalermsook, S. Heydrich, E. Holm, A. Karrenbauer, Nearly tight approximability results for minimum biclique cover and partition, In Proceedings of the 22nd Annual European Symposium on Algorithms (Wroclaw, 2014)

2014

Later among the works it cites.

K. Kubjas, E. Robeva, B. Sturmfels, Fixed points of the EM algorithm and nonnegative rank boundaries, Annals of Statistics

2015

Later among the works it cites.

Ya. Shitov, Nonnegative rank depends on the field, preprint (2015) arXiv:1505.01893

Original

2015

Later among the works it cites.

D. Chistikov, S. Kiefer, I. Marušić, M. Shirmohammadi, J. Worrell, Nonnegative Matrix Factorization Requires Irrationality, preprint (2016) arXiv:1605.06848

Original

2016

Closest in time.

J. Gouveia, H. Fawzi, R. Z. Robinson, Rational and real positive semidefinite rank can be different, Operations Research Letters