Annealed imitation: fast dynamics for maximum clique
Marcello Pelillo · 2004
We propose a new class of heuristics for the maximum clique problem (MCP) whose basic ingredients are: (1) a parameterized continuous formulation of MCP, (2) an instability analysis of equilibria of imitation dynamics from evolutionary game theory, and (3) a principled way of varying a regularization parameter during the evolution process so as to avoid inefficient solutions. The resulting annealed imitation" class is shown to contain algorithms that are dramatically faster than and as accurate as state-of-the-art neural network heuristics for maximum clique.