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