The complexity of approximating a nonlinear program
From MaRDI portal
Publication:1906280
DOI10.1007/BF01585569zbMath0839.90104MaRDI QIDQ1906280
Mihir Bellare, Phillip Rogaway
Publication date: 12 February 1996
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
probabilistically checkable proofs; interactive proof systems; polynomial time approximation; maximum of a multivariable polynomial inside a convex polytope
90C60: Abstract computational complexity for mathematical programming problems
90C30: Nonlinear programming
90C20: Quadratic programming
Related Items
On the advantage over a random assignment, Copositive optimization -- recent developments and applications, On the complexity of optimization over the standard simplex, Approximation results for the weighted \(P_4\) partition problem, The complexity of optimizing over a simplex, hypercube or sphere: a short survey, FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension, Complexity results for some global optimization problems, On the complexity of approximating a KKT point of quadratic programming, Differential approximation results for the traveling salesman problem with distances 1 and 2, A PTAS for the minimization of polynomials of fixed degree over the simplex
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Non-deterministic exponential time has two-prover interactive protocols
- Approximation algorithms for indefinite quadratic programming
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Constructing roadmaps of semi-algebraic sets. I: Completeness
- Structure preserving reductions among convex optimization problems
- On the power of multi-prover interactive protocols
- Fully parallelized multi-prover protocols for NEXP-time
- Multi-prover encoding schemes and three-prover proof systems
- Quadratic programming is in NP
- Improved non-approximability results
- The Knowledge Complexity of Interactive Proof Systems
- Two-Prover Protocols---Low Error at Affordable Rates
- On the hardness of approximating minimization problems
- Efficient probabilistically checkable proofs and applications to approximations
- Maxima for Graphs and a New Proof of a Theorem of Turán
