A New Trust Region Technique for the Maximum Weight Clique Problem

Stanislav Busygin (busygina-teleport.com)

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 new 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 graph vertices. It was implemented in a publicly available software package QUALEX-MS. Computational experiments evidence that the algorithm is exact on small graphs and exceptionally efficient on DIMACS benchmark graphs and various random maximum weight clique problem instances.

Keywords: maximum weight clique, continuous approach, Motzkin-Straus theorem, quadratic programming, heuristics, trust region, algorithms, NP-hard.

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Combinatorial Optimization (Approximation Algorithms )

Citation: Submitted to Special Issue of Discrete Applied Mathematics: Combinatorial Optimization 2002.

Download: [Postscript][Compressed Postscript]

Entry Submitted: 01/16/2002
Entry Accepted: 01/16/2002
Entry Last Modified: 09/18/2002

Modify/Update this entry