Combinatoire, algorithmique, structure et familles ordonnées d’ensembles au menu d'Oscar Defrain

Diplômé en informatique théorique de l’Université de Montpellier, Oscar Defrain a ensuite effectué une thèse en informatique au LIMOS, Université Clermont Auvergne, où il a étudié différents aspects algorithmiques d’un problème d’énumération dans les graphes, hypergraphes et treillis. Après un an de post-doc à l’Université de Varsovie sur des thématiques d’algorithmique FPT et de décompositions de graphes, il devient maître de conférence au LIS où il continue sa recherche entre combinatoire, algorithmique, structure et familles ordonnées d’ensembles au sein de l’équipe ACRO.   En informatique et en mathématiques discrètes, de nombreuses questions demandent de trouver la meilleure réponse parmi toutes celles disponibles. Connus sous le nom de problèmes d’optimisation, elles sont très courant en pratique : calcul du plus court chemin, du vol le moins cher, etc. En revanche, plutôt que de proposer une solution, il apparaît parfois préférable de les générer toutes, ou en partie. Ces questionnements, appelés problèmes d’énumération, se rencontrent également dans la vie de tous les jours : recherche de différents itinéraires, calcul des meilleures réponses à une requête, etc.   Les problèmes d’énumération restent pour certains encore très mal compris. C’est notamment le cas de la dualisation des fonctions monotones booléennes, pour laquelle le meilleur algorithme connu s’exécute en temps quasi-polynomial, et n’est pas combinatoire. Aujourd’hui central en algorithmique d’énumération, cet algorithme dû à Fredman et Khachiyan se retrouve utilisé comme brique de base pour résoudre de nombreux autres problèmes plus combinatoires : énumération des transversaux minimaux d’un hypergraphe, des dominants minimaux d’un graphe, des meet-irréductibles de certaines classes de treillis, etc. Néanmoins et malgré de nombreux efforts, la question de l’existence d’un algorithme polynomial pour la dualisation reste ouverte, et ce depuis plus de 30 ans.   « Dans mon projet de recherche, j’ai pour ambition de progresser sur ces questions dans des instances restreintes ou géométriques, afin de tirer profit de paramètres structurels, et de proposer des algorithmes combinatoires plus efficaces », explique Oscar Defrain. Pour cela, il pourra notamment compter sur la pluridisciplinarité des membres de l’équipe ACRO, et leurs affinités pour la géométrie et les structures ordonnées d’ensembles.