Optimisation combinatoire

Optimisation combinatoireCode de l'UE : HMIN332M

Présentation

Nous approfondirons tout d'abord les techniques classiques de conception d'algorithmes/schémas d'approximation (analyse d'algorithmes gloutons, programmation linéaire et arrondis, recherche locale, approximation duale, techniques de "guess",..), ainsi que des résultats de base sur l'inapproximabilité (typiquement introduction / transfert de gap). Nous nous intéresserons ensuite au cas de l'analyse on-line (les données ne sont pas connues à l'avance), de l'analyse multicritère (plusieurs critères antagonistes sont considérés). Enfin, nous présenterons quelques résultats d'approximation polynomiale liés à l'utilisation du rapport différentielle, alternative à la mesure classique. Ces techniques seront dans un premier temps introduites sur les problèmes de base du domaine (vertex cover and set cover, independent set, sac à dos, problèmes de packing,...). Puis, nous verrons comment les utiliser sur des problèmes plus spécifiques dans les réseaux et dans l'ordonnancement. Entre autres, nous étudierons certains problèmes de recouvrement sous contraintes (recouvrement des graphes, problème de Steiner sous contraintes de degré des sommets, multiples contraintes dans l'optimisation, ...).

Volume horaire

  • CM : 13.5
  • TD : 25.5
  • TP : 0
Diplômes intégrant cette UE

En bref

Crédits ECTS 5

Période de l'année
S3

Contact(s)

Contact(s) administratif(s)

Jean-claude KONIG (jean-claude.konig @ umontpellier.fr)