Résumé : Dans la littérature, on considère souvent qu'un algorithme d'approximation polynomial est plus performant qu'un autre lorsqu'il possède un meilleur rapport d'approximation en pire cas. Cependant, il faut être conscient que cette mesure, désormais "classique", ne prend pas en compte la réalité de toutes les exécutions possibles d'un algorithme (elle ne considère que les exécutions menant à la plus mauvaise solution). Dans mes travaux, je me suis focalisé sur le problème du vertex cover et j'ai tenté de mieux "capturer" le comportement des ces algorithmes d’approximation en montrant que les performances moyennes d’un algorithme peuvent être décorélées des performances en pire cas, en évaluant les performances moyennes d’un algorithme et en comparant les performances de différents algorithmes (analytiquement et expérimentalement). J'ai également proposé un algorithme de liste et j'ai prouvé analytiquement qu'il retourne toujours une meilleure solution que celle construite par un autre algorithme de liste récent [ORL 2006] quand ils traitent la même liste de sommets (dans certains graphes particuliers, la différence de taille peut être arbitrairement grande). On constate dans ces études que les algorithmes 2-approchés étudiés sont ceux qui obtiennent les plus mauvaises performances en moyenne et que ceux qui ont les meilleurs comportements moyens ont de mauvais rapports d'approximation.

Dernière modification : Monday 18 March 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr