Séminaire du LIF
Jeudi 20 février à 14h - Luminy, Amphi 12
Dominique Fortin
INRIA Rocquencourt
Régularisation de Maximum Clique
On considère un graphe simple G non orienté connexe et sans boucles ; une clique (resp. un stable) dans G est un ensemble de sommets 2 à 2 adjacents (resp. non adjacents). Cliques et stables se correspondant en passant au graphe complément, nous adoptons ici la formulation en clique plutôt qu'en stable. Une clique est maximale si elle n'est contenue dans aucune autre clique plus grande. Le problème max clique est de trouver dans G une clique de taille maximale. Ce problème s'étend au cas où les sommets sont pondérés, avec max clique pondéré.
Motzkin-Strauss [MS65], ont montré un résultat sur la taille des cliques maximales, mais leur solution est entachée de nombreux optima locaux parasites. Bomze [Bom97], a introduit une régularisation diagonale et raffiné le résultat de Motzkin-Strauss.
Nous poursuivons les mêmes idées de régularisation pour le cas pondéré à la fois diagonales et non diagonales en utilisant le complément de Perron. Nous explicitons aussi des heuristiques basées sur la région de confiance validées par Busygin [Bus01] en précisant l'influence des valeurs absolues de certaines valeurs propres.
Travail réalisé avec I. Tseveendorj. Mots clés : optimisation combinatoire, max clique, Perron-Frobenius, propriété de Monge.
Email : Dominique.Fortin@inria.fr
[MS65] T.S. Motzkin and E.G. Strauss. Maxima for graphs and a new proof of a theorem of turan, 1965.
[Bom97] I.M. Bomze. Evolution towards the maximum clique. Journal of Global Optimization, 10:143-164, 1997.
[Bus01] S. Busygin. A new trust region technique for maximum weight clique, 2001.