fr | en

Séparés par des virgules

Visioconférence | Soutenance de thèse de Madame Zhi LU

14h00 | Faculté des Sciences | 2, boulevard Lavoisier | ANGERS

Sujet : Optimization Approaches for Minimum Conductance Graph Partitioning

Directeur de thèse :
Monsieur Jin-Kao HAO

RÉSUMÉ

Le problème de partitionnement de graphe de conductance minimale (MCGPP) est un problème d’optimisation combinatoire NP-difficile avec de nombreuses applications pratiques dans divers domaines tels que la détection communautaire, la bioinformatique et la vision par ordinateur. Etant donnée sa complexité intrinsèque, des approches heuristiques et métaheuristiques constituent un moyen convenable pour résoudre des instances de grande taille. Cette thèse est consacrée au développement d’algorithmes métaheuristiques performants pour le MC-GPP. Plus précisément, nous proposons un algorithme «Stagnation aware Breakout Tabu Search», un algorithme évolutif hybride (MAMC) et un algorithme multiniveau basé sur le recuit simulé (IMSA). Nous présentons des résultats expérimentaux sur de nombreux graphes de grande dimension de la littérature ayant jusqu’à 23 millions de sommets. Nous montrons la haute performance de nos algorithmes par rapport à l’état de l’art. Nous analysons les éléments algorithmiques et stratégies de recherche pour mettre en lumière leur influence sur la performance des algorithmes proposés.

Télécharger l'avis de soutenance de thèse

Scroll