Computational complexity of norm-maximization
The paper is concerned with the computational complexity of the decision problem that arises in attempting to maximize a quasi-convex function \(\phi\) over a convex polytope P in n-space that is presented as the intersection of a finite number m of closed half spaces. This problem is NP-hard (for variable n) when \(\phi\) is the pth power of the classical p- norm. For this problem the question arises whether there exists \(y\in P\) such that \(\phi\) (y)\(\geq \beta\), where \(\beta\) is an integer. The present reexamination of the problem establishes NP-hardness for a wide 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. Some main conclusions are as follows: The problems of \(\{\)-1,1\(\}\)-maximization and \(\{\) 0,1\(\}\)-maximizatin of a positive definite quadratic norm are NP-complete. For maximizing the Euclidean norm over a rectangular parallelotope in \(R^ n\) there is an algorithm that uses only n inner-product computations and n-1 comparisons. The expositions assumes some familiarity with the classes P and NP, and with the rudiments of the theory of NP-completeness.
- `` Strong NP-Completeness Results
- A Compactness Theorem For Affine Equivalence-Classes of Convex Regions
- A new polynomial-time algorithm for linear programming
- A polynomial-time algorithm for a class of linear complementarity problems
- A solvable case of quadratic 0-1 programming
- A Variable-Complexity Norm Maximization Problem
- Algorithmes de calcul du maximum des formes quadratiques sur la boule unité de la norme du max
- An extension of Karmarkar's projective algorithm for convex quadratic programming
- Beliebige konvexe Polytope als Schnitte und Projektionen höherdimensionaler Würfel, Simplizes und Masspolytope
- Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
- Constrained global optimization: algorithms and applications
- Extreme varieties, concave functions, and the fixed charge problem
- Finding the convex hull facet by facet
- scientific article; zbMATH DE number 3120544 (Why is no real title available?)
- scientific article; zbMATH DE number 3677572 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3059362 (Why is no real title available?)
- Hyperrhombs inscribed to convex bodies
- Interior path following primal-dual algorithms. II: Convex quadratic programming
- MAXIMIZING A CONVEX QUADRATIC FUNCTION OVER A HYPERCUBE
- On the complexity of four polyhedral set containment problems
- Polynomial algorithms in linear programming
- Quasimonotone Boolean Functions and Bistellar Graphs
- Some NP-complete problems in quadratic and nonlinear programming
- The basic algorithm for pseudo-Boolean programming revisited
- The complexity of satisfiability problems
- The Complexity of Vertex Enumeration Methods
- The maximum numbers of faces of a convex polytope
- Unimodular functions
- Complexity results for some global optimization problems
- The computational complexity of maximization and integration
- Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
- On the complexity of some basic problems in computational convexity. I. Containment problems
- Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard
- Geometric optimization problems likely not contained in \(\mathbb A\mathbb P\mathbb X\)
- Largest \(j\)-simplices in \(n\)-polytopes
- Largest j-simplices in d-cubes: Some relatives of the Hadamard maximum determinant problem
- On the co-NP-completeness of the zonotope containment problem
- Fixed-parameter complexity and approximability of norm maximization
- On the entropy of couplings
- Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
- Complexity of unconstrained \(L_2 - L_p\) minimization
- The computational complexity of duality
- A Variable-Complexity Norm Maximization Problem
- Novel approaches to the discrimination problem
- scientific article; zbMATH DE number 3637739 (Why is no real title available?)
- Deterministic and randomized polynomial‐time approximation of radii
- Computing the norm ∥A∥∞,1 is NP-hard∗
- scientific article; zbMATH DE number 1560333 (Why is no real title available?)
- Two classes of games on polyhedral sets in systems economic studies
- Polynomial norms
- Distributionally Robust Linear and Discrete Optimization with Marginals
- On clustering bodies: geometry and polyhedral approximation
- Gradient free cooperative seeking of a moving source
- Deciding uniqueness in norm maximazation
- The computational complexity of the weak gravity conjecture
- Tolerance analysis in linear programming: searching for lower and upper bounds
This page was built for publication: Computational complexity of norm-maximization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q757258)
