Complexity results for some global optimization problems

DOI10.1007/s10957-008-9448-5zbMath1173.90545OpenAlexW2036807485MaRDI QIDQ1024247

Marco Locatelli

Publication date: 16 June 2009

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10957-008-9448-5

zbMATH Keywords

complexityglobal optimizationapproximation problemsseparable functions

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for indefinite quadratic programming
• Computational complexity of norm-maximization
• Quadratic programming with one negative eigenvalue is NP-hard
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• Approximating quadratic programming with bound and quadratic constraints
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• Geometric optimization problems likely not contained in \(\mathbb A\mathbb P\mathbb X\)
• The complexity of approximating a nonlinear program
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• \(NP\)-hardness of linear multiplicative programming and related problems
• Maxima for Graphs and a New Proof of a Theorem of Turán