Dimitrios M. Thilikos a reçu en septembre 2024 le prix EATCS-IPEC Nerode pour son article :
(Meta) Kernelization. J. ACM 63(5) : 44:1-44:69 (2016), annoncé à Foundations of Computer Science (FOCS) 2010,
co-écrit avec H.L. Bodlaender, F.V. Fomin, D. Lokshtanov, E. Penninkx, et S. Saurabh.
Le prix EATCS-IPEC Nerode est décerné aux articles les plus remarquables dans le domaine de l’algorithmique multivariée.
L’article a fourni le premier métathéorème algorithmique dans la théorie de la kernelisation. La kernelisation peut être considérée comme une théorie mathématique du prétraitement en temps polynomial, et est applicable dans plusieurs domaines tels que la conception d’algorithmes paramétrés, d’approximation et de heuristiques efficaces.
Les résultats de l’article ont fourni, pour la première fois, des conditions logiques/combinatoires générales qui impliquent automatiquement l’existence d’algorithmes de kernelisation pour une vaste famille de problèmes.
Lien: https://eatcs.org/index.php/home/1-news/2987-eatcs-ipec-nerode-prize-2024
Contact : dimitrios.thilikostouloupas@lirmm.fr
Site web : https://www.lirmm.fr/~thilikosto/
