PACKENUM
Deciphering the internalization profiles of mGlu receptors
MSCA Postdoctoral Fellowships 2022
Superviseur : SAU VALLS Ignasi
CNRS
LIRMM
Pôle de Recherche Mathématiques, Informatique, Physique, Systèmes
DESCRIPTION :
Les algorithmes jouent un rôle crucial dans de nombreux aspects de la vie de milliards de personnes à travers le monde. Beaucoup des problèmes que nous souhaitons résoudre, dans l’industrie comme dans le milieu académique, sont NP-difficiles, et l’on s’attend à ce qu’aucun algorithme en temps polynomial ne permette d’en obtenir une solution optimale. Pourtant, ces problèmes sont résolus des millions de fois chaque jour. Sans l’utilisation de techniques de prétraitement, leur résolution serait irréalisable : ces techniques réduisent considérablement les temps d’exécution et sont souvent indispensables pour résoudre un problème. Expliquer pourquoi ces méthodes fonctionnent en pratique, et concevoir de nouvelles méthodes assorties de garanties de performance, constitue un défi majeur en informatique théorique. Dans le cadre de la complexité paramétrée, ces techniques sont modélisées par la kernelisation, qui utilise une mesure supplémentaire de la structure du problème (le paramètre) pour produire une instance équivalente plus petite, pouvant être résolue rapidement.
Cependant, il existe généralement plusieurs solutions optimales, quel que soit le critère d’optimalité, et tirer des conclusions à partir d’une seule solution peut être trompeur. Il est donc nécessaire, dans de nombreux contextes, d’en savoir davantage sur l’ensemble des solutions optimales, ce qui peut être formalisé par des problèmes d’énumération. Contrairement aux problèmes de décision, on sait très peu de choses sur le prétraitement pour les problèmes d’énumération. Dans le concept récemment défini de noyau d’énumération, les solutions de l’instance réduite servent à partitionner et à énumérer efficacement l’ensemble des solutions de l’instance initiale.
Dans ce projet, le chercheur concevra et mettra en œuvre de nouveaux algorithmes paramétrés et de nouveaux noyaux pour les problèmes d’énumération, et développera la théorie des bornes inférieures nécessaire pour distinguer les problèmes qui admettent des noyaux d’énumération polynomiaux de ceux qui n’en admettent pas. Les noyaux conçus compteront parmi les premiers noyaux d’énumération, tandis que la théorie des bornes inférieures constituera un élément fondamental de la complexité paramétrée, permettant aux chercheurs d’identifier les problèmes qui n’admettent pas de prétraitement efficace et de concentrer leurs efforts sur ceux qui le permettent.
Informations sur le projet :
- Date de début : 8 juillet 2024
- Date de fin : 7 juillet 2026
- Coût total : 140 797,44€
- Coordonné par le CNRS
- Référence projet : 101109317
Mots-clés : Parameterized Complexity; Kernelization; Enumeration; Preprocessing.
