MALLEM Maher

PhD student
Team : RO
Arrival date : 10/01/2021
    Sorbonne Université - LIP6
    Boîte courrier 169
    Couloir 26-00, Étage 4, Bureau 404
    4 place Jussieu
    75252 PARIS CEDEX 05
    FRANCE

Tel: +33 1 44 27 87 41, Maher.Mallem (at) nulllip6.fr
https://lip6.fr/Maher.Mallem

Supervision : Claire HANEN

Parameterized complexity and efficient enumerative schemes for the RCPSP

L'étude de la complexité paramétrée de problèmes combinatoires permet de comprendre comment certains paramètres spécifiques à chaque problème influencent sa complexité.
Peu de résultats ont été publiés à ce jour dans le domaine de l'ordonnancement; la majorité des résultats obtenus concernent des problèmes d'optimisation combinatoires sur les graphes. La thèse aura en premier lieu pour objectif de développer si cela est possible de nouveaux algorithmes paramétrés, et dans le cas contraire, de démontrer qu'il n'en n'existe pas pour ce paramètre à moins que P=NP. Il s'agira alors de faire émerger une cartographie de la complexité paramétrée pour les problèmes d'ordonnancement issus du RCPSP.
Au delà d'algorithmes énumératifs visant à montrer l'existence d'algorithmes FPT, le second objectif de la thèse visera à concevoir des algorithmes efficaces en pratique fondés sur ces nouveaux paradigmes.