The complexity of approximating a nonlinear program

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)

zbMATH Keywords

probabilistically checkable proofsinteractive proof systemspolynomial time approximationmaximum of a multivariable polynomial inside a convex polytope

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Nonlinear programming (90C30) Quadratic programming (90C20)

Related Items

Proximity in concave integer quadratic programming, On the complexity of approximating a KKT point of quadratic programming, An approximation algorithm for indefinite mixed integer quadratic programming, 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, On the convergence rate of grid search for polynomial optimization over the simplex, A PTAS for the minimization of polynomials of fixed degree over the simplex, Subdeterminants and Concave Integer Quadratic Programming, Cheaper relaxation and better approximation for multi-ball constrained quadratic optimization and extension, On the advantage over a random assignment, Complexity results for some global optimization problems, An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex, Differential approximation results for the traveling salesman problem with distances 1 and 2

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