Algorithmes d'Approximation Sous-Exponentiels et Paramétrés – S-EX-AP-PE-AL

Le sujet de ce projet est la conception d’algorithmes d’approximation efficaces pour des problèmes NP-difficiles d’optimisation combinatoire. Ces problèmes se retrouvent dans la plupart des domaines scientifiques - en réalité, la grande majorité des problèmes intéressants sont NP-difficiles et par conséquent, n’admettent pas d'algorithmes exacts efficaces. Le besoin de résoudre ces problèmes a donc motivé l'élaboration d'algorithmes pouvant retourner des solutions sous-optimales (algorithmes d'approximation), ou des algorithmes pouvant utiliser d'avantage de temps (algorithmes en temps exponentiel ou paramétrés). Ces deux approches sont parmi les sujets les plus étudiés en informatique théorique. Elles ont permis des succès notables, mais ont maintenant atteint leurs limites. En particulier, grâce aux récents résultats en théorie de la complexité "fine" et en difficulté d'approximation, nous savons que de larges classes de problèmes sont difficiles à approximer en temps polynomial et difficiles à résoudre de manière exacte avec des algorithmes sous-exponentiels ou paramétrés (selon des conjectures standards).

Le projet SEXAPPEAL propose de dépasser ces barrières en adoptant une approche unifiée pour la conception d'algorithmes pour des problèmes NP-difficiles. Son hypothèse scientifique est que pour beaucoup de problèmes d'optimisation importants, trouver une solution presque optimale demande dramatiquement moins de temps que de résoudre le problème de manière exacte. Cette hypothèse est grandement étayée par des résultats récents de notre équipe. Ces travaux préliminaires indiquent qu'en combinant les techniques de l'approximation polynomiale avec celles des algorithmes exacts, il est possible de garantir une solution avec une qualité non réalisable en temps polynomial, souvent extrêmement proche de l'optimum, tout en investissant beaucoup moins de temps que pour résoudre le problème de manière exacte.

Notre projet propose de réunir des techniques qui ont été étudiées de manière disjointe dans les contextes des algorithmes exponentiels et paramétrés, et dans celui de l'approximation polynomiale. Nous proposons une méthodologie qui nous permettra des progrès rapides, tout en minimisant le risque, en orientant notre projet autour de trois Tâches:

1. Algorithmes d'approximation exponentiels/paramétrés pour des problèmes d'optimisation de réseaux
2. Techniques d'approximation génériques en temps super-polynomial
3. Bornes inférieures et difficulté d'approximation

La Tâche 1 se concentre sur la conception de nouveaux algorithmes pour des problèmes d'optimisation ayant des applications dans les réseaux de transports, de communications et sociaux, avec pour but d'améliorer le temps pris par les meilleurs algorithmes de résolution exacte et la qualité de la solution des meilleurs algorithmes d'approximation. Cette Tâche est un prolongement de travaux actuels et offre un potentiel de progrès rapides. Elle met également un accent significatif sur la conception logicielle, ce qui permettra de comparer nos travaux aux solutions de la littérature. La Tâche 2 se concentre sur un condensé des techniques algorithmiques découvertes dans la Tâche 1, la création de nouvelles techniques et leur formalisation précise dans des méta-théorèmes généraux. Enfin, la Tâche 3 vise à compléter le paysage en proposant des résultats de bornes inférieures sur l'approximation dans le contexte des algorithmes super-polynomiaux.

Ce projet est construit de manière à minimiser les risques tout en maximisant les gains, car le travail débutera avec une tâche construite sur des avancées récentes (Tâche 1), et culmine avec des Tâches plus ambitieuses (2 et 3) visant à produire une théorie complète unifiée pour faire face à la NP-difficulté. Notre équipe implique des chercheurs avec une expertise significative dans les domaines pertinents, et est conduite par un porteur ayant un dossier de recherche reconnu, particulièrement en phase avec le sujet de ce projet.