Les algorithmes
au cœur de la science des données
Comme domaine scientifique, l’algorithmique à garanties de performance puise dans la recherche opérationnelle et l’informatique théorique son inspiration, sa problématique et ses motivations, et rend à ces disciplines de nouveaux concepts et de puissants outils d’analyse et de résolution.
Complexité paramétrée
Résolution exacte et approchée
Garantie de performances
Algorithmique en ligne
Réoptimisation
Optimisation combinatoire
Méthode probabiliste
Applications
L’algorithmique fondamentale est au cœur des avancées en sciences des données comme discipline informatique.
Le domaine de l’algorithmique à garanties de performance met en synergie de nombreuses compétences issues en grande partie de la recherche opérationnelle et de l’informatique théorique : l’algorithmique, la théorie de la complexité, la programmation mathématique, les mathématiques discrètes et la combinatoire.
Ce champ de recherche permet ainsi d'étudier la résolution des problèmes difficiles par des algorithmes offrant des garanties de performance soit sur la qualité des solutions calculées, soit sur leurs temps d'exécution, soit sur la quantité de mémoire utilisée.
Nos recherches
dans les laboratoires de l'université
Les travaux de recherche menés à Dauphine – PSL sur ces thématiques se développent autour de quatre axes principaux :
- Approximation, domaine phare de l’activité des membres du LAMSADE depuis de nombreuses années. Le travail dans cet axe porte à la fois sur l’approximation polynomiale (qui inclue des approches plus récentes telles l’approximation multicritère, les problèmes labellisés et la robustesse) et l’approximation modérément exponentielle (domaine initié par les membres du LAMSADE) et paramétrée
- Résolution exacte et complexité
- Modèles d’optimisation pour des problèmes évolutifs (algorithmique online, réoptimisation et optimisation combinatoire probabiliste
- Jeux algorithmiques et optimisation combinatoire
Nos chercheurs
Cristina Bazgan, Aristotelis Giannakos, Laurent Gourvès, Ararat Harutyunyan, Eunjung Kim, Michail Lampis, Cécile Murat, Vangelis Th. Paschos, Florian Sikora
Exemples de travaux
- Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos : Structural parameters, tight bounds, and approximation for (k, r)-center. Discrete Applied Mathematics 264 : 90-117 (2019)
- Cristina Bazgan, Florent Foucaud, Florian Sikora. Parameterized and approximation complexity of Partial VC Dimension. Theor. Comput. Sci. 766 : 1-15 (2019)
- Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, Florian Sikora : Token Sliding on Split Graphs. STACS 2019 : 13 :1-13 :17
- Nicolas Bousquet, Louis Esperet, Ararat Harutyunyan, Rémi de Joannis de Velcros : Exact Distance Colouring in Trees. Combinatorics, Probability & Computing 28(2) : 177-186 (2019)
- Édouard Bonnet, Vangelis Th. Paschos : Sparsification and subexponential approximation. Acta Inf. 55(1) : 1-15 (2018)
- Michael Lampis : Finer Tight Bounds for Coloring on Clique-Width. ICALP 2018 : 86 :1-86 : 14