## 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 p^{th} 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 language | English |
---|---|

Pages (from-to) | 203-225 |

Number of pages | 23 |

Journal | Combinatorica |

Volume | 10 |

Issue number | 2 |

DOIs | |

State | Published - Jun 1990 |

Externally published | Yes |

## Keywords

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