Computational complexity of norm-maximization

H. L. Bodlaender, P. Gritzmann, V. Klee, J. Van Leeuwen

Research output: Contribution to journalArticlepeer-review

45 Scopus citations

Abstract

This paper discusses the problem of maximizing a quasiconvex function φ over a convex polytope P in n-space that is presented as the intersection of a finite number of halfspaces. The problem is known to be NP-hard (for variable n) when φ is the pth power of the classical p-norm. The present reexamination of the problem establishes NP-hardness for a wider class of functions, and for the p-norm it proves the NP-hardness of maximization over n-dimensional parallelotopes that are centered at the origin or have a vertex there. This in turn implies the NP-hardness of {-1, 1}-maximization and {0, 1}-maximization of a positive definite quadratic form. On the "good" side, there is an efficient algorithm for maximizing the Euclidean norm over an arbitrary rectangular parallelotope.

Original languageEnglish
Pages (from-to)203-225
Number of pages23
JournalCombinatorica
Volume10
Issue number2
DOIs
StatePublished - Jun 1990
Externally publishedYes

Keywords

  • AMS subject classification (1980): 90C30, 68Q15, 52A25, 90C20, 90C09, 52A20

Fingerprint

Dive into the research topics of 'Computational complexity of norm-maximization'. Together they form a unique fingerprint.

Cite this