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] |

| ===== 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 plan**. **See 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 period**, **Tuesday, 12:45-15:45. The tentative schedule is as follows: ** | + | ****Where**?** **Sophie Germain building**, **room 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 building**, **room 1004**. | + | ****When**?** **First period**, **Wednesdays, 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. |

| * 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**: |

- | * **basics**: **polytopes **and **simplicial complexes, examples and properties**; | + | * **Classification of surfaces ** |

- | * **planar triangulations, flips, and Delaunay triangulation;** | + | ** * Computing with cut locus**: **shortest non-contractible **and **non-separating closed curve**; **shortest cut graph** |

- | * **more combinatorial structures**: **permutohedra and associahedra.** | + | * **Deciding homotopy with universal covers** |

- | * **Advanced algorithms for geometric **graphs (**VCA)**: | + | * **If time**: **minimum (s,t)-cut on surfaces, or tightening curves on surfaces ** |

- | ** *** **Advanced algorithms for **planar graphs: **Approximation algorithms**, **Baker's technique**, **fixed-parameter tractability;** | + | ** ** |

- | ** *** **Advanced algorithms **for low-dimensional Euclidean **inputs: Approximation schemes for TSP**, **local **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 set**, **dominating set**, **vertex cover). Generalization to facility location.** |

| + | ** *** **The power of local search **for **clustering problems: ** |

| + | ** * facility location in **low-dimensional Euclidean **space**, **decomposition 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 ==== |