A Variable-Complexity Norm Maximization Problem

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 1, the problem is shown to be NP-complete. For the ∞-norm, the problem can be solved in polynomial time. The problem of finding an upper bound to the largest norm for any p ∈ [ 1,∞ ] can be solved in polynomial time by solving a single linear program.