arXiv Analytics

Sign in

arXiv:1605.04000 [math.CO]AbstractReferencesReviewsResources

A short proof that NMF is NP-hard

Yaroslav Shitov

Published 2016-05-12Version 1

We give a short combinatorial proof that the nonnegative matrix factorization is an NP-hard problem. Moreover, we prove that NMF remains NP-hard when restricted to 01-matrices, answering a recent question of Moitra.

Comments: 2 pages
Categories: math.CO, cs.CC
Related articles: Most relevant | Search more
arXiv:1207.4884 [math.CO] (Published 2012-07-20, updated 2014-05-16)
A short proof for the polyhedrality of the Chvátal-Gomory closure of a compact convex set
arXiv:0906.4769 [math.CO] (Published 2009-06-25)
A Short Proof of Gamas's Theorem
arXiv:0911.2809 [math.CO] (Published 2009-11-14, updated 2012-03-06)
A short proof of the tree-packing theorem

Links

Toolbox