The complexity of approximating a nonlinear program
From MaRDI portal
Publication:1906280
DOI10.1007/BF01585569zbMATH Open0839.90104MaRDI QIDQ1906280FDOQ1906280
Authors: M. Bellare, Phillip Rogaway 
Publication date: 12 February 1996
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Recommendations
- Complexity and algorithms for nonlinear optimization problems
- Approximation methods for problems of nonlinear programming
- scientific article; zbMATH DE number 847149
- The complexity of a special convex programming problem connected with nonlinear optimization
- An approximate algorithm for nonlinear integer programming
- An approximate algorithm for nonlinear integer programming
- scientific article; zbMATH DE number 1944142
- The approximation algorithm for solving a sort of non-smooth programming
- Approximation to nonproper problems of convex programming
- On the complexity of nonlinear mixed-integer optimization
interactive proof systemsprobabilistically checkable proofspolynomial time approximationmaximum of a multivariable polynomial inside a convex polytope
Quadratic programming (90C20) Nonlinear programming (90C30) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Structure preserving reductions among convex optimization problems
- Maxima for Graphs and a New Proof of a Theorem of Turán
- Non-deterministic exponential time has two-prover interactive protocols
- Approximation algorithms for indefinite quadratic programming
- Improved non-approximability results
- Title not available (Why is that?)
- On the hardness of approximating minimization problems
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- The Knowledge Complexity of Interactive Proof Systems
- Efficient probabilistically checkable proofs and applications to approximations
- The complexity of approximating a nonlinear program
- Quadratic programming is in NP
- Constructing roadmaps of semi-algebraic sets. I: Completeness
- On the power of multi-prover interactive protocols
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fully parallelized multi-prover protocols for NEXP-time
- Title not available (Why is that?)
- Two-Prover Protocols---Low Error at Affordable Rates
- Multi-prover encoding schemes and three-prover proof systems
Cited In (36)
- FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
- Intractability of approximate multi-dimensional nonlinear optimization on independence systems
- A PTAS for the minimization of polynomials of fixed degree over the simplex
- Title not available (Why is that?)
- An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex
- Geometric optimization problems likely not contained in \(\mathbb A\mathbb P\mathbb X\)
- An approximation algorithm for indefinite mixed integer quadratic programming
- A well-characterized approximation problem
- Title not available (Why is that?)
- The complexity of optimizing over a simplex, hypercube or sphere: a short survey
- Copositive optimization -- recent developments and applications
- Approximate parametric searching
- Subdeterminants and concave integer quadratic programming
- Proximity in concave integer quadratic programming
- On the space complexity of linear programming with preprocessing
- NP-hardness of deciding convexity of quartic polynomials and related problems
- Cheaper relaxation and better approximation for multi-ball constrained quadratic optimization and extension
- Complexity of approximating bounded variants of optimization problems
- Title not available (Why is that?)
- On the advantage over a random assignment
- An Analysis of Approximate Nonlinear Elimination
- Trigonometric approximation of the max-cut polytope is star-like
- Obfuscation of pseudo-deterministic quantum circuits
- Differential approximation results for the traveling salesman problem with distances 1 and 2
- On the complexity of optimization over the standard simplex
- Complexity results for some global optimization problems
- On the complexity of testing attainment of the optimal value in nonlinear optimization
- Separation between estimation and approximation
- Approximation results for the weighted \(P_4\) partition problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the complexity of approximating a KKT point of quadratic programming
- On the Complexity of Computing Two Nonlinearity Measures
- On the convergence rate of grid search for polynomial optimization over the simplex
- Cost approximation algorithms with nonmonotone line searches for a general class of nonlinear programs
- Title not available (Why is that?)
This page was built for publication: The complexity of approximating a nonlinear program
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1906280)
