Column subset selection is NP-complete

DOI10.1016/j.laa.2020.09.015zbMath1456.68056arXiv1701.02764MaRDI QIDQ2228097

Yaroslav N. Shitov

Publication date: 16 February 2021

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

NP-completeness; column subset selection

Mathematics Subject Classification ID

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

65F99: Numerical linear algebra

Uses Software

• Algorithm 853