Algorithmes évolutifs et axés sur les données pour les problèmes d'optimisation dans les flux de graphes dynamiques // Scalable and Data-Driven Algorithms for Optimization Problems in Dynamic Graph Streams

Le problème d'affectation est un problème d'optimisation fondamental qui trouve des applications dans la logistique, l'allocation des ressources et, plus récemment, les systèmes énergétiques. Les solutions traditionnelles reposent sur la disponibilité d'une mémoire suffisante pour stocker et traiter toutes les données d'entrée - nœuds, arêtes et poids. Cependant, à l'ère actuelle des ensembles de données massives, cette hypothèse n'est plus réalisable. Le modèle de semi-streaming offre une solution prometteuse, fonctionnant avec des contraintes de mémoire qui évoluent linéairement avec le nombre de nœuds, tout en traitant les données d'arêtes de manière dynamique à mesure qu'elles arrivent dans un flux.

Ce projet de doctorat vise à concevoir des algorithmes innovants adaptés au modèle de semi-streaming, en mettant l'accent sur le traitement des flux de graphes dynamiques. La recherche combinera des connaissances théoriques avec des applications pratiques pour faire progresser l'évolutivité et l'efficacité des algorithmes pour les problèmes d'affectation et d'autres problèmes d'optimisation dans des environnements contraints.

-----
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

The assignment problem is a foundational optimization problem with applications across logistics, resource allocation, and, more recently, energy systems. Traditional solutions rely on the availability of sufficient memory to store and process all input data—nodes, edges, and weights. However, in today's era of massive datasets, this assumption is no longer feasible. The semi-streaming model offers a promising solution, operating within memory constraints that scale linearly with the number of nodes while handling edge data dynamically as it arrives in a stream.

This PhD project aims to design innovative algorithms tailored to the semi-streaming model, with a focus on handling dynamic graph streams. The research will combine theoretical insights with practical applications to advance the scalability and efficiency of algorithms for assignment problems and other optimization problems in constrained environments.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Début de la thèse : 01/10/2025

Public funding alone (i.e. government, region, European, international organization research grant)

Concours pour un contrat doctoral

Université de Bordeaux

39 Mathématiques et Informatique

Nous recherchons un candidat motivé et enthousiaste, titulaire d'un master en informatique ou en mathématiques (ou sur le point de l'être). De bonnes connaissances dans au moins un des grands domaines de la proposition (théorie des graphes/combinatoire, algorithmes/complexité) sont requises. Une expérience préalable dans des projets de programmation, en particulier des problèmes d'optimisation et/ou de graphes, est un atout. De bonnes aptitudes à la communication orale et écrite sont essentielles. -----
We are seeking a motivated and enthusiastic candidate with a completed (or about to be completed) Master degree in computer science or mathematics. Good knowledge in at least one of the broad areas of the proposal (graph theory/combinatorics, algorithms/complexity) is required. Previous experience in programming projects, especially optimization problems and/or graph problems, is a plus. Good verbal and written communication skills are essential.