A Variable-Complexity Norm Maximization Problem
Olvi L. Mangasarian, T.-H. Shiau · SIAM Journal on Algebraic and Discrete Methods · 1986
The decision problem associated with the problem of finding a point with largest norm in a bounded polyhedral set is shown to have a considerable range of complexity depending on the norm employed. For a p-norm with integer $p\geqq 1$, the problem is shown to be NP-complete. For the $\infty $-norm, the problem can be solved in polynomial time. The problem of finding an upper bound to the largest norm for any $p \in [ 1,\infty ]$ can be solved in polynomial time by solving a single linear program.