Computing the norm ∥A∥∞,1 is NP-hard∗

From MaRDI portal
Publication:4498326





The author proves that computing the subordinate norm \(\|A \|_{\infty,1}\) is NP-hard. Existence of a polynomial-time algorithm for computing this norm with relative accuracy \(1/(4n^2)\), where \(n\) is the matrix size, implies P=NP.




Cited in
(21)








This page was built for publication: Computing the norm ∥A∥∞,1 is NP-hard∗

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4498326)