Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-2-38-1 [2018/11/20 13:01]
pilaud [What's new?]
cours:c-2-38-1 [2019/09/10 13:28] (current)
colin [Course notes]
Line 1: Line 1:
 ===== Algorithmique et combinatoire des graphes géométriques / Algorithms and combinatorics for geometric graphs (24h) ===== ===== Algorithmique et combinatoire des graphes géométriques / Algorithms and combinatorics for geometric graphs (24h) =====
  
-Course 2-38-1, year 2018-2019.+Course 2-38-1, year 2019-2020.
  
-Teachers: [[https://www.di.ens.fr/~vcohen/|Vincent Cohen-Addad]] (CNRS & Université Paris 6 Pierre et Marie Curie) and [[http://www.lix.polytechnique.fr/~pilaud/|Vincent Pilaud]] (teacher in charge of the course, CNRS & École Polytechnique). +Teachers: [[https://www.di.ens.fr/~vcohen/|Vincent Cohen-Addad]] (CNRS & Université Paris 6 Pierre et Marie Curie) and [[http://monge.univ-mlv.fr/~colinde/|Éric Colin de Verdière]] (CNRS & Université Paris-Est Marne-la-Vallée).
-==== What's new? ====+
  
-**Careful: the schedule has changed from the initial planSee the Practical information section.**+Teacher in charge of the course, not teaching this year:  
 +[[http://www.lix.polytechnique.fr/~pilaud/|Vincent Pilaud]] (CNRS & École Polytechnique). 
 +==== What's new? ====
  
-The course starts on Tuesday September 11, from 12:45 to 15:45 in room 1004 of the Sophie Germain building.+The course starts on Wednesday, September 11.
  
-The [[http://www.lix.polytechnique.fr/~pilaud/enseignement/MPRI/devoirMaisonMPRI18A.pdf|first exercice sheet]] (for VP's course) was provided on September 18 and due on October 2. +The final exam will be on November 13 or 20, usual time and room.
- +
-The [[|second exercice sheet]] (for VCA's course) was provided on October 9 and due on October 23. +
- +
-The [[http://www.lix.polytechnique.fr/~pilaud/enseignement/MPRI/devoirMaisonMPRI18B.pdf|third exercice sheet]] (for VP's course) was provided on October 23 and due on November 6. +
- +
-The final exam will be on November 20, usual time (12:45-16:45) and usual room (Sophie Germain building, room 1004). All documents and manuscript notes from the course are allowed. All other documents or electronic devices are forbidden. Plan to prepare two separated sheets for the two parts of the exam.+
 ==== Practical information ==== ==== Practical information ====
  
-**When?** First periodTuesday, 12:45-15:45. The tentative schedule is as follows: +**Where?** Sophie Germain buildingroom 1013.
-  * Sept 11. VCA (basic properties of planar graphs) + VP (planar graphs, crossing lemma) +
-  * Sept 18. VP (Schnyder woods) +
-  * Sept 25. NO LECTURE. +
-  * Oct 2. VCA (planarity testing, graph drawing) + VP (Polytopes I) +
-  * Oct 9. VCA (minimum spanning tree and separators of planar graphs + more algorithms for planar graphs: coloring, min-cut) +
-  * Oct 16. VCA (Advanced algorithms for planar graphs I) + VP (Polytopes II) +
-  * Oct 23. VP (Triangulations + secondary polytope) +
-  * Oct 30. VCA (Advanced algorithms for planar graphs II) +
-  * Nov 6. VP (Permutahedra & associahedra) +
-  * Nov 13. VP (Brick polytopes) +
-  * Nov 20. Exam +
-Note that this tentative schedule is subject to modifications.+
  
-**Where?** Sophie Germain buildingroom 1004.+**When?** First periodWednesdays, 12:45-15:45.  Typically, each 3-hour lecture will be split into two parts, each taught by one of the teachers.
  
 **Language.** Lessons will be given in French by default, or in English upon request of at least three persons who do not understand French, and if nobody objects.  Lecture notes will be available in English.  The exam will be translated if needed. **Language.** Lessons will be given in French by default, or in English upon request of at least three persons who do not understand French, and if nobody objects.  Lecture notes will be available in English.  The exam will be translated if needed.
  
-**Evaluation.** The evaluation is done with the final exam.  Three exercises sheets will be proposed during the course period; if solved, they will give some extra credit for the final grade. The tentative schedule of the exercice sheets is as follows: +**Evaluation.** The evaluation is done with the final exam.  Three exercises sheets will be proposed during the course period; if solved, they will give some extra credit for the final grade.
-  * Sept 18. [[http://www.lix.polytechnique.fr/~pilaud/enseignement/MPRI/devoirMaisonMPRI18A.pdf|Short exercice sheet for VP's course]], to return on Oct 2. +
-  * Oct 9. [[|Long exercice sheet for VCA's course]], to return on Oct 23. +
-  * Oct 23. [[http://www.lix.polytechnique.fr/~pilaud/enseignement/MPRI/devoirMaisonMPRI18B.pdf|Long exercice sheet for VP's course]], to return on Nov 6. +
-  * Nov 20. Final exam (usual time, usual room).   All documents and manuscript notes from the course are allowed. All other documents or electronic devices are forbidden. Plan to prepare two separated sheets for the two parts of the exam.                         +
  
 **Prerequisites.** None. **Prerequisites.** None.
Line 51: Line 30:
   * to see some relatively standard tools in algorithms and combinatorics applied in geometric settings,   * to see some relatively standard tools in algorithms and combinatorics applied in geometric settings,
   * leading to results at the edge of current research, and   * leading to results at the edge of current research, and
-  * to learn about some fundamental objects such as polytopes and surfaces, which appear in various contexts (optimization, discrete mathematics, topological graph theory).+  * to learn about some fundamental concepts which appear in various contexts (optimization, discrete mathematics, topological graph theory).
  
 ==== Preliminary roadmap ==== ==== Preliminary roadmap ====
  
-  * Graphs drawn in the plane (VCA + VP):+The two parts of the course are relatively independent, except for the basics taught by ECV. 
 + 
 +ECV's part: 
 +  * Graphs drawn in the plane:
     * basics: combinatorial representations of planar graphs, topology, duality, Euler's formula;     * basics: combinatorial representations of planar graphs, topology, duality, Euler's formula;
     * planarity test and graph drawing algorithms;     * planarity test and graph drawing algorithms;
-    * crossing numbers of graphs; 
     * efficient exact algorithms for planar graphs: minimum spanning tree, vertex coloring, minimum (s,t)-cut.     * efficient exact algorithms for planar graphs: minimum spanning tree, vertex coloring, minimum (s,t)-cut.
-  * Polytopes and geometric graphs (VP)+  * Graphs drawn on surfaces
-    * basicspolytopes and simplicial complexes, examples and properties+    * Classification of surfaces 
-    * planar triangulations, flips, and Delaunay triangulation; +    * Computing with cut locusshortest non-contractible and non-separating closed curveshortest cut graph 
-    * more combinatorial structurespermutohedra and associahedra. +    * Deciding homotopy with universal covers 
-  * Advanced algorithms for geometric graphs (VCA)+    * If timeminimum (s,t)-cut on surfaces, or tightening curves on surfaces 
-    Advanced algorithms for planar graphs: Approximation algorithmsBaker's techniquefixed-parameter tractability; + 
-    Advanced algorithms for low-dimensional Euclidean inputs: Approximation schemes for TSPlocal search techniques for clustering problems.+VCA's part: 
 + 
 +  * Balanced Separators of planar graphs, r-division, and algorithmic applications (e.g.approximation algorithm for the independent set problem). 
 +  The power of local search in planar graphs: a paradigm to solve various optimization problems (independent setdominating setvertex cover). Generalization to facility location. 
 +  The power of local search for clustering problems: 
 +    * facility location in low-dimensional Euclidean spacedecomposition of Voronoi diagrams. 
 +    * facility location in general metrics. 
 +  * Metric embeddings and their algorithm applications: Johnson-Lindenstrauss; metric embedding into tree metrics. 
 +  * Locality sensitive hashing and nearest neighbor search. 
 ==== Course notes ==== ==== Course notes ====
  
-VP's notes can be found [[http://www.lix.polytechnique.fr/~pilaud/enseignement/MPRI/notesCoursMPRI18.pdf|here]].+ECV's notes can be found [[http://monge.univ-mlv.fr/~colinde/cours/19mpri/poly.pdf|here]].
  
 ==== Bibliography ==== ==== Bibliography ====
  
   * The course notes (since no book covers all these topics).   * The course notes (since no book covers all these topics).
-  * Jesus A. De Loera, Jörg Rambau, and Francisco Santos. Triangulations: Structures for Algorithms and Applications, volume 25 of Algorithms and Computation in Mathematics. Springer Verlag, 2010. 
-  * Stefan Felsner. Geometric graphs and arrangements. Advanced Lectures in Mathematics. Friedr. Vieweg & Sohn, Wiesbaden, 2004. Some chapters from combinatorial geometry. 
   * Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, 2001.   * Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, 2001.
-  * Günter M. Ziegler. Lectures on polytopes, volume 152 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995.+  * more to come for VCA's course; stay tuned.
  
 ==== Relevant courses ==== ==== Relevant courses ====
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA