Doctorant en informatique (H/F) - algorithmique pour problèmes d'optimisation sur les graphes d[...]

Doctorant en informatique (H/F) - algorithmique pour problèmes d'optimisation sur les graphes dirigés Cette offre est disponible dans les langues suivantes : Date Limite Candidature : vendredi 28 juin 2024 23:59:00 heure de Paris Assurez-vous que votre profil candidat soit correctement renseigné avant de postuler Informations généralesIntitulé de l'offre : Doctorant en informatique (H/F) - algorithmique pour problèmes d'optimisation sur les graphes dirigés Référence : UMR6158-FLOFOU-001Nombre de Postes : 1Lieu de travail : AUBIERE Date de publication : vendredi 7 juin 2024 Type de contrat : CDD Doctorant/Contrat doctoral Durée du contrat : 36 moisDate de début de la thèse : 1 octobre 2024Quotité de travail : Temps complet Rémunération : La rémunération est de 2135,00 € bruts mensuels (environ 1650,00€ nets) Section(s) CN : Sciences de l'information : fondements de l'informatique, calculs, algorithmes, représentations, exploitations Description du sujet de thèse Un grand nombre de problèmes fondamentaux d'optimisation combinatoire sont NP-difficiles sur les graphes dirigés (digraphes). Cela inclut les problèmes du Directed Feedback Vertex/Arc Set (3,4), des chemins sommets/arcs disjoints (2), de la couverture par chemins (1,2), et bien d'autres. Améliorer les algorithmes d'approximation ou paramétrés pour ces problèmes, lorsque l'entrée peut être n'importe quel digraphe, constitue un problème bien connu et ouvert de longue date. Cela motive l'étude de ces problèmes sur des classes de digraphes structurés, où ils demeurent NP-difficiles, mais sont susceptibles d'admettre des algorithmes d'approximation et paramétrés non-triviaux, comme dans (1,2,3,4). L'objectif de cette thèse de doctorat sera d'explorer le côté algorithmique des problèmes fondamentaux d'optimisation sur les digraphes. À cette fin, nous développerons de nouveaux algorithmes et des bornes inférieures pour ces problèmes sur différentes classes de digraphes structurés (tournois, digraphes semi-complets, digraphes planaires ou triangulés, etc). Nous nous concentrerons sur deux lignes de recherche :1. Algorithmes d'approximation : l'objectif est de concevoir des algorithmes en temps polynomial pour produire des solutions d'approximation de facteur constant ou O(log n) pour des entrées de taille n.2. Algorithmes paramétrés : l'objectif est de concevoir des algorithmes qui calculent une solution exacte de taille au plus k en temps f(k)poly(n), où f est une fonction à croissance (modérément) exponentielle de k et poly, un polynôme.(1) M. Caceres, M. Cairo, B. Mumey, R. Rizzi, and A.I. Tomescu. Sparsifying, shrinking and splicing for minimum path cover in parameterized linear time. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pp. 359–376.(2) H. Fernau, F. Foucaud, K. Mann, U. Padariya and R. Rao. Parameterizing path partitions. Proceedings of the 13th International Conference on Algorithms and Complexity (CIAC 2023), Lecture Notes in Computer Science 13898:187-201, 2023.(3) M. Kumar and D. Lokshtanov. Faster exact and parameterized algorithm for feedback vertex set in tournaments. Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016. LIPIcs 47, pp. 49:1–49:13, 2016.(4) D. Lokshtanov, P. Misra, J. Mukherjee, F. Panolan, G. Philip and S. Saurabh. 2-approximating Feedback Vertex Set in tournaments. ACM Transactions on Algorithms17(2): 11:1-11:14, 2021. Contexte de travail La thèse sera dirigée par Laurent BEAUDOU (LIMOS) et co-encadrée par Florent FOUCAUD (LIMOS) et Pranabendu MISRA (Chennai Mathematical Institute, Inde). En raison de cette composante internationale, la personne recrutée devra idéalement être prête à effectuer plusieurs séjours de quelques semaines à Chennai en Inde.La thèse aura une durée de 3 ans et sera effectuée au LIMOS (site d'Aubière, en banlieue de Clermont-Ferrand).Le début du contrat est idéalement le 1er octobre 2024, un début un peu plus tardiv est aussi possible. Informations complémentaires La personne recrutée devra être diplômée d'un master en informatique ou mathématiques (ou sujet connexe), et avoir des connaissances préalables en théorie des graphes et en algorithmique. De bonnes connsaissances en théorie structurelle des graphes, en graphes dirigés, en algorithmique d'approximation et/ou en algorithmique paramétrée sera un plus.La maîtrise de l'anglais (oral et écrit) est nécessaire.Merci de candidater en joignant un CV, un relevé des notes de master disponibles, et une courte lettre de motivation. Mentionner 1 ou 2 personnes référentes que nous pouvons contacter pour obtenir une recommandation.Les candidatures seront examinées à partir du 17 juin 2024 jusqu'à ce que le poste soit pourvu.Les candidats (H/F) intéressés peuvent envoyer un email informel pour obtenir des informations avant de déposer leur candidature. #J-18808-Ljbffr