Name
Abstract | ||
|---|---|---|
This paper discusses the problem of maximizing a quasiconvex function phi 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 phi 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. |
Year | DOI | Venue |
|---|---|---|
1990 | 10.1007/BF02123011 | COMBINATORICA |
Keywords | Field | DocType |
positive definite,computational complexity,quadratic form | Discrete mathematics,Combinatorics,Quadratic form,Nonlinear programming,Euclidean distance,Positive-definite matrix,Quasiconvex function,Convex polytope,Maximization,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
10 | 2 | 0209-9683 |
Citations | PageRank | References |
16 | 2.06 | 17 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hans L. Bodlaender | 1 | 5699 | 375.15 |
| Peter Gritzmann | 2 | 412 | 46.93 |
| Victor Klee | 3 | 169 | 17.23 |
| Jan Van Leeuwen | 4 | 2002 | 521.25 |