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\geqq 1$, the problem is shown to be NP-complete. For the $\infty $-norm, ... View More