Publié le 24 mai 2023
– Mis à jour le 7 juin 2023
Exponential Lower Bounds for Polytopes in Combinatorial Optimization, un article dont Samuel Fiorini (Département de Mathématique) et Serge Massar (Département de Physique) de la Faculté des Sciences (ULB) sont co-auteurs.
Le prix Gödel récompense des articles exceptionnels dans le domaine de l’informatique théorique et est parrainé conjointement par l'European Association for Theoretical Computer Science (EATCS) et le Special Interest Group on Algorithms and Computation Theory for Computing Machinery (ACM SIGACT). Ce prestigieux prix est remis chaque année, la présentation ayant lieu alternativement au Colloque international EATCS on Automata, Languages, and Programming (ICALP) et au ACM Symposium on Theory of Computing (STOC).
Pour 2023, il a été décerné aux articles suivants :
L’optimisation combinatoire est un problème central de l’algorithmique, avec des applications extrêmement nombreuses et importantes. Par exemple minimiser le temps que les chauffeurs mettent pour distribuer des paquets à domicile, tenant compte des distances entre maisons, du trafic attendu, de la nécessité de faire des pauses, etc.. peut se formuler comme un problème d’optimisation combinatoire.
L’une des méthodes les plus efficaces pour résoudre un de ces problèmes est de lui associer un polytope (convexe), dans un espace de grande dimension, et d’optimiser une fonction linéaire sur ce polytope. Les polytopes convexes sont des objets géométriques ayant des sommets, arêtes, et côtés (ou facettes, pour utiliser le terme technique d’usage), comme par exemple un cube, un tétraèdre, ou bien une pyramide. Ceci lie la complexité algorithmique du problème à la structure géométrique du polytope associé.
Une question fondamentale du domaine est de comprendre la structure des polytopes associés aux problèmes canoniques du domaine, comme le problème du voyageur du commerce, ou le problème du couplage parfait dans un graphe. Samuel Fiorini, Serge Massar et leurs co-auteurs ont montré que toute formulation étendue du polytope associé au problème du voyageur du commerce a une taille exponentielle, résolvant ainsi un problème ouvert depuis 30 ans. Ce résultat montre que ces polytopes ont une structure très complexe : non seulement, ils ont un nombre exponentiel de facettes mais tout polytope de dimension supérieure (appelé formulation étendue) dont l’image par projection est un de ces polytopes a également un nombre exponentiel de facettes. Ceci montre que l’approche géométrique décrite ci-dessus pour résoudre le problème du voyageur du commerce ne peut pas fournir d’algorithme qui soit efficace dans tous les cas, et ce même en passant par une formulation étendue.
Quelques années plus tard, Thomas Rothvoss (Université de Washington) a montré que toute formulation étendue du polytope associé à au problème du couplage parfait (pour lequel il existe un algorithme efficace) a également une taille exponentielle.
Ce 31ème Prix Gödel sera décerné lors du ACM Symposium on Theory of Computing (STOC), qui aura lieu à Orlando, en Floride, du 20 au 23 juin 2023.
