DocumentCode
1915682
Title
Annealed imitation: fast dynamics for maximum clique
Author
Pelillo, Marcello
Author_Institution
Dipt. di Informatica, Universita Ca´´ Foscari di Venezia, Venezia Mestre, Italy
Volume
1
fYear
2003
fDate
20-24 July 2003
Firstpage
55
Abstract
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.
Keywords
game theory; graph theory; neural nets; evolutionary game theory; fast annealed imitation dynamics; instability analysis; maximum clique problem; neural network heuristics; regularization parameter; Annealing; Equations; Game theory; Neural networks; Quadratic programming;
fLanguage
English
Publisher
ieee
Conference_Titel
Neural Networks, 2003. Proceedings of the International Joint Conference on
ISSN
1098-7576
Print_ISBN
0-7803-7898-9
Type
conf
DOI
10.1109/IJCNN.2003.1223289
Filename
1223289
Link To Document