CE48 - Fondements du numérique: informatique, automatique, traitement du signal

Un Parcours par les Limites de l'Efficacité – ELIT

Résumé de soumission

L'objectif de cette proposition est d'explorer les limites de la traitabilité des problèmes de calcul pour y découvir de dichotomies de complexité, en particulier dans les domaines peu explorés jusqu'à présent, et sous l'angle de la complexité paramétrée. En d'autres termes, notre objectif est de nous attaquer à de problèmes pour lesquels il manque une distinction claire entre les cas "faciles" et "difficiles". Nous prévoyons de focaliser nos recherches sur les cinq tâches suivantes: algorithmes paramétrés pour interdire certaines structures dans un graphe, existence de noyaux polynomiaux pour de paramètres structuraux, dichotomies de complexité pour les CSPs, optimilité des algorithmes utilisant des paramètres de largeur pour les graphes denses, et algorithmes efficaces dans les graphes dirigés. Pour atteindre ces objectifs, le consortium s'articule autour du coordinateur scientifique, avec des collaborateurs français et étrangers bien choisis pour mener à bien ce programme.

Coordination du projet

Ignasi Sau (Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier)

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

CNRS-LIRMM Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier

Aide de l'ANR 168 923 euros
Début et durée du projet scientifique : septembre 2021 - 48 Mois

Liens utiles

Explorez notre base de projets financés

 

 

L’ANR met à disposition ses jeux de données sur les projets, cliquez ici pour en savoir plus.

Inscrivez-vous à notre newsletter
pour recevoir nos actualités
S'inscrire à notre newsletter