A new deterministic annealing algorithm for maximum clique

We propose a new heuristic for approximating the maximum clique problem based on a recently introduced deterministic annealing algorithm which generalizes Waugh and Westewelt´s cluster-competitive net. The approach is centered around a fundamental result proved by Motzkin and Straus in the mid-1960s, and recently expanded in various ways, which allows us to formulate the maximum clique problem in terms of a linearly constrained quadratic program. Preliminary experiments on random as well as standard benchmark graphs are presented which demonstrate the validity of the approach