Continuous Characterizations of the Maximum Clique Problem
Continuous Characterizations of the Maximum Clique Problem
复制标题
DOI：
10.1287/moor.22.3.754
复制
发表时间：
1997-08
期刊：
影响因子：
--
通讯作者：
Luana E. Gibbons;D. Hearn;P. Pardalos;M. Ramana
中科院分区：
文献类型：
--
作者：
Luana E. Gibbons;D. Hearn;P. Pardalos;M. Ramana
给定一个邻接矩阵为A的图G，最大团问题的Motzkin-Strauss公式是二次规划max{xTAx <$xTe = 1，x ≥ 0}。众所周知，该QP的全局最优值为1-1/ωG，其中ωG为G的团数.在这里，我们描述了与上述QP有关的以下性质：1一阶最优性，2二阶最优性，3局部最优性，4严格局部最优性。这些特征揭示了有趣的底层离散结构，并且是多项式时间可验证的。的Motzkin-Strauss QP的参数化，然后介绍和它的性质进行了研究。最后，Motzkin-Strauss公式的一个扩展提供了一个图的加权团数。
Given a graph G whose adjacency matrix is A, the Motzkin-Strauss formulation of the Maximum-Clique Problem is the quadratic program max{xTAx ∣ xTe = 1, x ≥ 0}. It is well known that the global optimum value of this QP is 1-1/ωG, where ωG is the clique number of G. Here, we characterize the following properties pertaining to the above QP: 1 first order optimality, 2 second order optimality, 3 local optimality, 4 strict local optimality. These characterizations reveal interesting underlying discrete structures, and are polynomial time verifiable. A parametrization of the Motzkin-Strauss QP is then introduced and its properties are investigated. Finally, an extension of the Motzkin-Strauss formulation is provided for the weighted clique number of a graph.