DEA Algo , Cours sur les algorithmes d'approximation

Enseignante : Claire Kenyon, Laboratoire de Recherche en Informatique, bat 490, 91405 Orsay Cedex. Email: claire.kenyon@lri.fr
Calendrier : Il y aura 20 heures de cours, a peu pres repartis en dix seances de cours de 2 heures, les jeudi de 10h40 a 12h40, salle 11 couloir 65-66 a Jussieu. A priori on s'oriente sur un cours le Me 6/2 a 10h40, pas de cours le jeudi 14/2, et une seance de 4h le 21/2 -- a confirmer.
Jeudi 13/12: Introduction, programmation dynamique, suite de Fibonacci, sac a dos, schema d'approximation pour le sac a dos, arbre couvrant de cout minimum, graphes euleriens, 2-approximation pour le tour du voyageur de commerce metrique.
Jeudi 20/12: couplages parfaits de poids minimum, 3/2-approximation pour le tour du voyageur de commerce metrique, schema d'approximation pour le tour du voyageur de commerce euclidien en dimension 2. Ordonnancement de taches pour minimiser le temps de completion maximal : 2-approximation de Graham, schema d'approximation.
Jeudi 10/1: schema d'approximation de Fernandez de la Vega et Lueker pour le bin-packing (Vazirani chapitre 9); schema d'approximation de Fernandez de la Vega et Kenyon pour MaxCut euclidien planaire.
Jeudi 17/1 Vazirani chapitres 1 et 2 : 2-approximation pour ensemble transversal (vertex cover), ln(n)-approximation pour couverture par ensembles (set cover), application = 2 ln(n)-approximation pour "shortest superstring".
Jeudi 24/1 Programmation lineaire. Principe de l'algorithme du simplexe (exemple tire du livre de Chvatal "linear programming"). Application de la programmation lineaire a l'approximation : 2-approximation pour couverture par sommets par "LP-rounding", O(log n)-approximation randomisee pour couverture par ensembles via "randomized rounding" (Vazirani chapitre 14).
Jeudi 31/1 Methode des esperances conditionnelles : Max Sat (Vazirani chapitre 6). Programmation semi-definie (Vazirani chapitre 26).
(Attention a la date et au lieu !) Mercredi 6/2 a 10h40, salle 203/205 au batimant 41. Vazirani chapitre 28.1 (comptage de solutions de formules DNF). Maxcut dans les graphes denses : algorithme de Goldreich, Goldwasser et Ron.
Jeudi 7/2 Vazirani chapitre 12.1, exo 12.10, et chapitre 15.
Jeudi 14/2: pas de cours
Jeudi 21/2: seance de 4h, jeudi 8h40-12h40, consacree aux presentations d'articles par les etudiants (voir planning un peu plus bas).
Bibliographie : La principale reference bibliographique est le livre de Vijay Vazirani, Approximation Algorithms, Springer-Verlag 2001, ISBN 3-540-65367-8. Ses notes de cours ne sont desormais plus accessibles sur le web; en revanche il y a de nombreuses references de notes de cours sur les algorithmes d'approximation, proches de mon cours. Par exemple, voir les notes de cours de Williamson ou de Cheriyan et Ravi.
Contenu du cours : Pour resoudre des problemes d'optimisation qui sont NP-difficiles ou qui n'ont pas d'algorithme polynomial connu, il est naturel de rechercher une solution approximative, avec borne sur l'erreur relative entre la qualite de la solution produite par l'algorithme par rapport a la valeur de la solution optimale. Nous etudierons diverses techniques pour concevoir des algorithmes d'approximation, au travers d'exemples representatifs : Coupe de valeur maximum pour separer $n$ points dans le plan euclidien , et recherche exhaustive; Probleme du sac a dos, et programmation dynamique; Probleme du ``Broadcast'' dans un reseau, et arrondi probabiliste; Bin-packing et programmation lineaire; Diffusion de donnees sur un canal, et relaxation lagrangienne; Codes de Huffman avec lettres de co\^uts differents, et relaxation adh oc; Couverture de sommets par ensembles, et dualite de la programmation lineaire.
Evaluation : Les etudiants auront un article a lire et a presenter avec rapport ecrit. Les articles sont accessibles a partir des liens ci-dessous. Vous pouvez eventuellement presenter un article en dehors de ceux de cette liste (si vous vous interessez particulierement a un domaine dans lequel il y a des algorithmes d'approximation, mais non represente dans la liste), a condition qu'il porte sur les algorithmes d'approximation et que vous me le montriez auparavant pour que j'y jette un coup d'oeil.
En pratique, ce travail se fera en binomes. Jeudi 6 fevrier, vous me donnez la liste des binomes et le titre de l'article lu par chaque binome. Jeudi 21/2, soutenances toute la matinee et remise du rapport au moment de la soutenance. Ces soutenances font partie du cours : vous devez assister aux soutenances les uns des autres.
Pour la soutenance, il est fortement conseille d'utiliser des transparents.
Vous devez 1) lire 2) ecrire et 3) parler.
1) Lire l'article (ou la partie de l'article qui vous interesse) en detail, c'est-a-dire:
- verifier tous les calculs, completer les preuves qui ne seraient qu'esquissees, corriger les "bugs" eventuels, aller consulter des references si necessaires (pour avoir le contexte et la motivation du probleme, la preuve de NP-completude, la preuve de tel ou tel theoreme utilise dans l'article...).
- Apres ce premier debroussaillage, vous devez reflechir a l'interet de l'article de facon plus creative : par exemple, en essayant divers exemples d'instances interessantes ; des variantes que vous pouvez imaginer, soit pour l'algorithme (marchent-elles ou pas ? Pourquoi ? Sont-elles plus rapides, plus simples ?), soit pour le probleme (l'algorithme peut-il etre adapte pour resoudre un probleme proche ?); en implementant et testant l'algorithme; y a-t-il un probleme plus simple pour lequel l'algorithme est plus facile a comprendre, plus intuitif ? Etc. Ce sont quelques suggestions de questions pouvant vous aider a comprendre l'article plus en profondeur.
2) Ecrire le rapport : il est conseille de le taper a la machine (en Latex par exemple : vous aurez de toute facon besoin d'apprendre Latex pour votre these, et c'est ideal pour ecrire des formules mathematiques). Vous n'etes pas oblige de faire un rapport sur la totalite de l'article: dans le cas d'articles touffus ou resolvant plusieurs problemes, vous pouvez tres bien choisir une partie de l'article seulement. Ce rapport doit tout d'abord comporter un resume de l'article ou de la partie d'article que vous avez lue, resume d'au plus une page : Definition du probleme, motivation, resultat nouveau, methode utilisee. Ensuite, les "details" (eventuellement consequents) par lesquels vous avez du completer l'article : signaler les erreurs, donner une preuve plus simple que celle de l'article ou une preuve manquante pour un lemme, parler de resultats dans des references bibliographiques que vous auriez ete amenes a consulter. Ceci peut faire typiquement entre 1 et 2 pages. Enfin, une partie "ouverte" ou vous faite part de vos reflexions. Pour un travail vraiment satisfaisant (pour esperer obtenir une note >14), c'est la la partie essentielle du rapport.
3) Parler pendant la soutenance : a priori je prevois environ 25 minutes par binome. La presence des deux binomes est indispensable a priori (sauf exception motivee). Prevoir environ 12 a 15 transparents. La presentation doit etre faite non pas pour moi mais pour les autres etudiants du cours. L'aspect pedagogique est primordial (et sera primordial dans la notation : votre presentation est confuse et me donne l'impression que les etudiants y assistant ont perdu leur temps, vous serez bien sur penalises). Il ne s'agit pas de m'impressionner par vos connaissances, mais d'enseigner quelque chose a vos camarades. Donc : prendre son temps, ne pas vouloir trop en faire, eviter les notations mathematiques, etre tres concret, faire des exemples, choisir une seule idee et centrer l'expose autour de cette idee a faire passer (ce peut etre une idee de comment modeliser un probleme applique, ou une idee algorithmique, ou une idee dans l'analyse, ou autre); bien structurer son expose, ecrire assez gros et lisible, parler de maniere intelligible, utiliser des feutres de couleurs, faire des schemas ou croquis, garder le contact avec l'auditoire et s'assurer que les gens suivent (le fait que les gens ne posent pas de questions signifie habituellement qu'ils sont perdus), etc. Pour faire une bonne soutenance, il est necessaire mais non suffisant d'avoir lu et compris l'article presente.
Programme des presentations d'articles du Jeudi 21 fevrier
8h40 Steve Oudot, facility location (Shmoys et al)
9h15 Hugo Gimbert et Alex Stanger, low-degree spanning trees of small weight
9h50 Alexandre Popescu et Eugene Tarassov, Average completion times
10h25 Vincent Bernat et Nathalie Bertrand, Superstrings
11h Behshad Behzadi et Daniel Ivan, Min Latency
11h35 K.-F. Lin et Daniel Goncalves, "Primal-dual parallel approximation technique applied to weighted set and vertex cover."
12h10 Mickael Delarbre et Thomas Deneux, Huffman
- Lasse Rempe, bin covering (rapport uniquement)
Pour m'envoyer un mail : cliquer ici
Liste des etudiants suivant le cours: 
ivan@poly.polytechnique.fr fayollej@cicrp.jussieu.fr 
houtmann@dptmaths.ens-cachan.fr nathalie.bertrand@crans.org 
deneux@clipper.ens.fr michael.delarbre@cicrp.jussieu.fr 
steve.oudot@ensta.fr vialette@liafa.jussieu.fr 
serre@liafa.jussieu.fr bernat@free.fr another_lin@yahoo.com 
m.korzen@caramail.com alexei_stanger11@yahoo.com 
gimbert@dptmaths.ens-cachan.fr lasse@lri.fr
popescu@poly.polytechnique.fr   alexei_stanger11@yahoo.com 
behshad.behzadi@polytechnique.fr goncalve@rip.ens-cachan.fr 
olivon@ifrance.com m.korzen@commail.com
Stages de DEA proposes: cliquer ici
Quelques articles parmi lesquels choisir un article a lire et a presenter :