A new trust region technique for the maximum weight clique problem
Discret. Appl. Math., 154 (15):
2080--2096 (October 2006)DOI: http://dx.doi.org/10.1016/j.dam.2005.04.010
Abstract
A new simple generalization of the Motzkin–Straus theorem for the maximum weight clique problem is formulated and directly proved. Within this framework a trust region heuristic is developed. In contrast to usual trust region methods, it regards not only the global optimum of a quadratic objective over a sphere, but also a set of other stationary points of the program. We formulate and prove a condition when a Motzkin–Straus optimum coincides with such a point. The developed method has complexity O( n 3 ) , where n is the number of vertices of the graph. It was implemented in a publicly available software package QUALEX-MS. Computational experiments indicate that the algorithm is exact on small graphs and very efficient on the DIMACS benchmark graphs and various random maximum weight clique problem instances.
