Deciding uniqueness in norm maximazation

DOI10.1007/BF01581081zbMath0789.90090MaRDI QIDQ687086

Victor Klee, Peter Gritzmann

Publication date: 12 June 1994

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

polytopeNP-hardnesssystem of linear inequalities

Mathematics Subject Classification ID

Convex programming (90C25) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Abstract computational complexity for mathematical programming problems (90C60) Nonlinear programming (90C30) Quadratic programming (90C20)

Related Items

On the complexity of some basic problems in computational convexity. I. Containment problems, Largest \(j\)-simplices in \(n\)-polytopes, Largest \(j\)-simplices in \(d\)-cubes: Some relatives of the Hadamard maximum determinant problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computational complexity of norm-maximization
• NP is as easy as detecting unique solutions
• The complexity of optimization problems
• Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
• Complexity of uniqueness and local search in quadratic 0-1 programming
• Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
• On the complexity of unique solutions
• Some NP-complete problems in quadratic and nonlinear programming