Automne 2023 - Manuel Lafond
Courriel: manuel.lafond@USherbrooke.ca

Mon local: D4-2010
Notes de cours
Exercices
Cours en ligne passés (APPROX)
Cours en ligne passés (FPT)
Quelques proposition de projet
Problèmes théoriques ouverts
Projets pratiques
  • Évaluez la pertinence de la kernelisation. Par exemple, implémentez un algo de branchement et évaluez le temps. Ensuite, implémentez un noyau et exécutez l'algo de branchement sur le noyau. Est-ce qu'un gain de temps est observé? Aussi, est-ce qu'on devrait appeler la procédure de noyau à chaque appel récursif, ou seulement au début?
  • Prenez un problème, étudié en classe ou non, et implémentez 2 ou 3 algos FPT. Évaluez la taille de données que vous pouvez tolérer, et comparez les temps d'exécution. Bien sûr, il est préférable d'étudier un nouveau problème.
Quelques sujets possibles d'articles
  • Les problèmes de clustering. Deux problèmes sont populaires: CLUSTER-EDITING et CORRELATION CLUSTERING.
    Voir cet article pour démarrer.
  • Le problème de la plus courte super-séquence (shortest superstring).
    Voir ce tutoriel pour y voir plusieurs références.
  • Il y a toute une historique d'algorithmes d'approximation pour Min-TSP et Max-TSP (TSP = traveling salesperson). Vous devriez pouvoir trouver des références facilement.
  • SET-COVER et ses variantes.
    Par exemple, la couverture maximum, ou encore le partial set cover.
  • Les problèmes de scheduling. Il y a beaucoup de variantes.
    Comme point de départ, je vous propose une thèse qui en explique beaucoup.
  • Il y a aussi plusieurs articles de type "survey". Ils sont souvent trop longs, mais l'idée serait de choisir un ensemble de résultats à présenter. Par exemple:
    Local ratio survey
    Randomized rounding survey
    Bin Packing survey
    Network design survey
    (et autres, cherchez 'approximation algorithms survey' sur google)