TY - JOUR
T1 - Improved semidefinite approximation bounds for nonconvex nonhomogeneous quadratic optimization with ellipsoid constraints
AU - Hsia, Yong
AU - Wang, Shu
AU - Xu, Zi
N1 - Publisher Copyright:
© 2015 Elsevier B.V. All rights reserved.
PY - 2015/5/30
Y1 - 2015/5/30
N2 - We study the problem of approximating nonconvex quadratic optimization with ellipsoid constraints (ECQP) and establish a new semidefinite approximation bound, which greatly improves Tseng's result (Tseng, 2003). As an application, we strictly improve the approximation ratio for the assignment-polytope constrained quadratic program. Finally, based on a randomized algorithm, we obtain a new approximation bound for (ECQP) which is sharp in the order of the number of the ellipsoid constraints.
AB - We study the problem of approximating nonconvex quadratic optimization with ellipsoid constraints (ECQP) and establish a new semidefinite approximation bound, which greatly improves Tseng's result (Tseng, 2003). As an application, we strictly improve the approximation ratio for the assignment-polytope constrained quadratic program. Finally, based on a randomized algorithm, we obtain a new approximation bound for (ECQP) which is sharp in the order of the number of the ellipsoid constraints.
KW - Approximation algorithm
KW - Quadratic constrained quadratic programming
KW - Semidefinite programming relaxation
UR - https://www.scopus.com/pages/publications/84930208970
U2 - 10.1016/j.orl.2015.05.002
DO - 10.1016/j.orl.2015.05.002
M3 - 文章
AN - SCOPUS:84930208970
SN - 0167-6377
VL - 43
SP - 378
EP - 383
JO - Operations Research Letters
JF - Operations Research Letters
IS - 4
ER -