ASSAYAKH Imad

Ma thèse a pour titre "Garantie de performance des algorithmes robustes pour la résolution de problèmes d'optimisation combinatoire avec des données imprécises et changeantes".

La grande majorité des problèmes d'ordonnancement et presque tous les problèmes de sac à dos sont NP-difficiles. Ainsi, la plupart des recherches théoriques visent à obtenir des solutions approximatives avec une déviation garantie de l'optimalité (analyse du pire cas), mais dans de nombreux problèmes, la limite classique du pire cas peut être assez grande, même pour les algorithmes qui se comportent bien dans les applications pratiques. L'objectif de ma recherche est de considérer d'autres mesures que l'analyse du pire cas pour juger de la qualité d'un algorithme d'approximation pour les problèmes d'ordonnancement et de sac à dos. Comme la distribution des données est pratiquement très difficile à prévoir, nous considérerons un cadre général où les données sont imprécises et où seules leurs bornes inférieures et supérieures sont connues. Deux critères seront étudiés : la minimisation du regret maximum et l'approximation différentielle, mais nous avons l'intention de définir de nouveaux critères complémentaires. La comparaison et l'analyse statistique des comportements des différents critères entre eux seront également considérées.