Quadratic maximization and semidefinite relaxation
Quadratic maximization and semidefinite relaxation
复制标题
DOI：
10.1007/s101070050006
复制
发表时间：
2000-05
影响因子：
2.7
通讯作者：
Shuzhong Zhang
中科院分区：
文献类型：
--
作者：
Shuzhong Zhang
本文研究了一类二次极大化问题及其半定规划松弛问题。对于一个特殊的子类的问题，我们表明，SDP松弛提供了一个精确的最优解。另一个子类是？？硬，保证SDP松弛产生近似解，最坏情况下的性能比为0.87856....这是Goemans和威廉姆森关于最大割问题的著名结果的推广。最后，我们讨论了这些结果的存在下，某种类型的符号限制的扩展。
In this paper we study a class of quadratic maximization problems and their semidefinite programming (SDP) relaxation. For a special subclass of the problems we show that the SDP relaxation provides an exact optimal solution. Another subclass, which is ??-hard, guarantees that the SDP relaxation yields an approximate solution with a worst-case performance ratio of 0.87856.... This is a generalization of the well-known result of Goemans and Williamson for the maximum-cut problem. Finally, we discuss extensions of these results in the presence of a certain type of sign restrictions.