David COUDERT / Nathann COHEN

Responsabilités

Directeur de recherche Inria / Chargé de recherche CNRS
Laboratoire d’Informatique, Signaux et Systèmes de Sophia Antipolis (I3S)
Institut national de la recherche en informatique et en automatique (Inria)

Distinctions

  • Vainqueurs du Flinders Hamiltonian Cycle Project (FHCP) Challenge

Biographie

David Coudert est Directeur de Recherche Inria. Il dirige l’équipe-projet COATI, commune à Inria et au laboratoire I3S (UNS, CNRS). Ses recherches portent sur l’algorithmique des graphes et l’optimisation combinatoire avec des applications dans les réseaux de communications et de transports.

Nathann Cohen est Chargé de Recherche CNRS au Laboratoire de Recherche en Informatique à Paris XI, en visite de longue durée à I3S. Ses recherches portent sur la théorie des graphes et l’optimisation combinatoire.

Le challenge international proposé par l’université Flinders d’Adelaïde (Australie) portait sur le problème du Cycle Hamiltonien. C’est un problème classique en théorie des graphes, réputé très difficile à résoudre. Il est aussi célèbre sous sa variante du problème du voyageur de commerce qui doit honorer de nombreux rendez-vous dans des villes éloignées sans jamais retourner sur ses pas.
L’équipe du Flinders Hamiltonian Cycle Project (FHCP) a lancé un défi à tous les chercheurs du domaine en leur proposant de résoudre 1001 instances de grandes tailles (jusqu’à 10 000 sommets) et en récompensant l’équipe de chercheurs qui parviendrait à trouver une solution pour tous les graphes proposés dans le délai du concours (1 an).

Nathann Cohen et David Coudert ont remporté ce challenge en résolvant 985 instances. Pour cela, ils ont combiné de multiples méthodes d’exploration, de décomposition et d’optimisation sur les graphes.