MATRIX p-NORMS ARE NP-HARD TO APPROXIMATE IF p ≠ 1, 2, ∞

被引：77

作者：

Hendrickx, Julien M. ^{[1
]}

Olshevsky, Alex ^{[1
]}

机构：

[1] MIT, Informat & Decis Syst Lab, Cambridge, MA 02139 USA

来源：

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS | 2010年 / 31卷 / 05期

基金：

美国国家科学基金会;

关键词：

matrix norms; complexity; NP-hardness;

D O I：

10.1137/09076773X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We show that, for any rational p is an element of [1, infinity) except p = 1, 2, unless P = NP, there is no polynomial time algorithm which approximates the matrix p-norm to arbitrary relative precision. We also show that, for any rational p is an element of [1, infinity) including p = 1, 2, unless P = NP, there is no polynomial-time algorithm which approximates the infinity, p mixed norm to some fixed relative precision.

引用

页码：2802 / 2812

页数：11

共 5 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[2] Some optimal inapproximability results [J].

Håstad, J .

JOURNAL OF THE ACM, 2001, 48 (04) :798-859

[3] SOME NP-COMPLETE PROBLEMS IN QUADRATIC AND NONLINEAR-PROGRAMMING [J].

MURTY, KG ;

KABADI, SN .

MATHEMATICAL PROGRAMMING, 1987, 39 (02) :117-129

[4] Computing the norm ||A||∞,1 is NP-hard [J].

Rohn, J .

LINEAR & MULTILINEAR ALGEBRA, 2000, 47 (03) :195-204

[5]

Steinberg Daureen, 2005, Computation of matrix norms with applications to robust optimization

← 1 →