Computational complexity of norm-maximization

DOI10.1007/BF02123011zbMath0722.90080OpenAlexW2022029673WikidataQ59568056 ScholiaQ59568056MaRDI QIDQ757258

Hans L. Bodlaender, Peter Gritzmann, Jan van Leeuwen, Victor Klee

Publication date: 1990

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02123011

zbMATH Keywords

NP-completenessNP-hardnessquasi-convex function

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces, On the complexity of some basic problems in computational convexity. I. Containment problems, Largest \(j\)-simplices in \(n\)-polytopes, Two Classes of Games on Polyhedral Sets in Systems Economic Studies, On clustering bodies: geometry and polyhedral approximation, Largest \(j\)-simplices in \(d\)-cubes: Some relatives of the Hadamard maximum determinant problem, Distributionally Robust Linear and Discrete Optimization with Marginals, Novel approaches to the discrimination problem, Gradient free cooperative seeking of a moving source, Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces, Deciding uniqueness in norm maximazation, Deterministic and randomized polynomial‐time approximation of radii, Complexity results for some global optimization problems, On the co-NP-completeness of the zonotope containment problem, Fixed-parameter complexity and approximability of norm maximization, On the entropy of couplings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Beliebige konvexe Polytope als Schnitte und Projektionen höherdimensionaler Würfel, Simplizes und Masspolytope
• Algorithmes de calcul du maximum des formes quadratiques sur la boule unité de la norme du max
• Unimodular functions
• A solvable case of quadratic 0-1 programming
• Constrained global optimization: algorithms and applications
• An extension of Karmarkar's projective algorithm for convex quadratic programming
• Interior path following primal-dual algorithms. II: Convex quadratic programming
• A polynomial-time algorithm for a class of linear complementarity problems
• Hyperrhombs inscribed to convex bodies
• The basic algorithm for pseudo-Boolean programming revisited
• Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
• The Complexity of Vertex Enumeration Methods
• Finding the convex hull facet by facet
• On the complexity of four polyhedral set containment problems
• A Variable-Complexity Norm Maximization Problem
• Some NP-complete problems in quadratic and nonlinear programming
• Extreme varieties, concave functions, and the fixed charge problem
• MAXIMIZING A CONVEX QUADRATIC FUNCTION OVER A HYPERCUBE
• Quasimonotone Boolean Functions and Bistellar Graphs
• Polynomial algorithms in linear programming
• `` Strong NP-Completeness Results
• The complexity of satisfiability problems
• The maximum numbers of faces of a convex polytope
• A Compactness Theorem For Affine Equivalence-Classes of Convex Regions