Abstract
NP-hardness is established for the problem whose instance is a system of linear inequalities defining a polytope P, and whose question is whether, on P, the global maximum of the Euclidean norm is attained at more than one vertex of P. The NP-hardness persists even for the restricted problem in which P 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.
| Original language | English |
|---|---|
| Pages (from-to) | 203-214 |
| Number of pages | 12 |
| Journal | Mathematical Programming |
| Volume | 57 |
| Issue number | 1-3 |
| DOIs | |
| State | Published - May 1992 |
| Externally published | Yes |
Keywords
- AMS Subject Classifications: 90C30, 68Q15, 90C20, 90C25, 52A25
- NP-hardness
- circumradius
- diameter
- global optimization
- inradius
- norm
- parallelotope
- polytope
- quadratic programming
- unique optimum
- width
Fingerprint
Dive into the research topics of 'Deciding uniqueness in norm maximization'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver