Semidefinite relaxation for two mixed binary quadratically constrained quadratic programs: algorithms and approximation bounds

DOI10.1007/s40305-015-0082-2zbMath1342.90129arXiv1403.3998OpenAlexW2131899619MaRDI QIDQ2630836

Mingyi Hong, Zi Xu

Publication date: 22 July 2016

Published in: Journal of the Operations Research Society of China (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1403.3998

zbMATH Keywords

NP-hardapproximation boundnonconvex quadratically constrained quadratic programmingsemidefinite program relaxation

Mathematics Subject Classification ID

Semidefinite programming (90C22) Quadratic programming (90C20) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Semidefinite approximation bound for a class of nonhomogeneous nonconvex quadratically constrained quadratic programming problem

Uses Software

• CVX

Cites Work

• Unnamed Item
• Unnamed Item
• Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations
• Extending the QCR method to general mixed-integer programs
• A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid
• Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
• On maximization of quadratic form over intersection of ellipsoids with common center
• Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations
• The MILP Road to MIQCP
• Semidefinite Approximation for Mixed Binary Quadratically Constrained Quadratic Programs
• Nonlinear Integer Programming
• Semidefinite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Robust Solutions of Uncertain Quadratic and Conic-Quadratic Problems
• Approximation Bounds for Quadratic Optimization with Homogeneous Quadratic Constraints
• A .699-approximation algorithm for Max-Bisection.