Name
Abstract | ||
|---|---|---|
NP-hardness is established for the problem whose instance is a system of linear inequalities defining a polytopeP, and whose question is whether, onP, the global maximum of the Euclidean norm is attained at more than one vertex ofP. The NP-hardness persists even for the restricted problem in whichP is a full-dimensional parallelotope with one vertex at the origin. This makes it possible to establish NP-hardness for other uniqueness problems, including some from pseudoboolean programming and computational convexity. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1007/BF01581081 | Math. Program. |
Keywords | Field | DocType |
circumradius.,polytope,diameter,norm,quadratic programming,width,unique optimum,global optimization,inradius,norm maximization,np-hardness,parallelotope,quadratic program,circumradius | Uniqueness,Discrete mathematics,Combinatorics,Mathematical optimization,Convexity,Vertex (geometry),Uniqueness theorem for Poisson's equation,Euclidean distance,Quadratic programming,Linear inequality,Maximization,Mathematics | Journal |
Volume | Issue | ISSN |
57 | 2 | 1436-4646 |
Citations | PageRank | References |
2 | 0.44 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Gritzmann | 1 | 412 | 46.93 |
| Victor Klee | 2 | 169 | 17.23 |