Lectures and Schedule with Materials

Below you find the schedule for 2017-2018.

Links to the slides and relevant materials will be added or updated during the course.
Week nr Lecture on tuesday by Johan van Rooij Lecture on thurday by Hans Bodlaender
46
November 14th
Introduction.
Slides: PPTX, PDF.
Stable Mariage Problem.
Slides: PPTX, PDF (first part).
Further reading:
  • Kleinberg and Tardos: Chapter 1.
November 16th
Flows and Matchings I: Maximum Flow
Slides: PPTX, PDF.
Further reading:
  • Cormen et al.: Chapter 26
  • Ahuja et al.
  • Schrijver: Chapters 10 and 11.
47
November 21st
Stable Roommates Problem.
Slides: PPTX, PDF (second part).
Further reading:
  • Robert W. Irving, An efficient algorithm for the "Stable Roommates" problem, Journal of Algorithms 6, 577-595, 1985. (ScienceDirect)
Shortest Paths: Algorithms for Standard Variants.
Slides: PPTX, PDF (first part).
Further reading:
  • Cormen et al.: Chapters 24 en 25.
  • Schrijver: Chapters 7 and 8.
November 23th
No course today
48
November 28th
Advanced Shortest Paths Algorithms.
Slides: PPTX, PDF (second part).
Further reading:
  • Cormen et al.: Chapters 24 en 25.
  • Schrijver: Chapters 7 and 8.
Introduction to Exact Exponential-Time Algorithms.
Slides: PPTX, PDF (first part).
Further reading:
  • Fomin and Kratsch: Chapters 1 and 3.
  • Sections 1-3 from: Gerard Woeginger, Exact Algorithms for NP-hard problems. "Combinatorial Optimization - Eureka! You shrink!". LNCS 2570, 185-207, 2003. (Download from TU/e).
November 30th
Teacher: Tom van der Zanden.
Flows and Matchings II: Minimum Cost Flow.
Slides:PPTX, PDF.
Further reading:
  • Ahuja et al.
  • Schrijver: Chapter 12.
Flows and Matchings III: Matching
Slides: PPTX, PDF.
Graph Isomorphism.
Slides: PPTX, PDF.
49
December 5th
Some Techniques for Exact Exponential-Time Algorithms.
Slides: PPTX, PDF (second part)
Further reading:
  • Fomin and Kratsch: Chapters 2, 8, 9
  • Sections 4-6 from: Gerard Woeginger, Exact Algorithms for NP-hard problems. "Combinatorial Optimization - Eureka! You shrink!". LNCS 2570, 185-207, 2003. (Download from TU/e).
December 7th
Flows (preflow push); Mininimum Cost flow; Graph Isomorphism.
Slides: See above
Further reading:
  • See above.
50
December 12th
Inclusion/Exclusion.
Slides: PPTX, PDF (third part).
Further reading:
  • Fomin and Kratsch: Chapter 4.
  • Cygan et al.: Section 10.1.
Measure-and-Conquer Analysis for Exact Exponential-Time Algorithms.
Slides: PPTX, PDF (fourth part).
Further reading:
  • Fomin and Kratsch: Chapter 6.
December 14th
Flows and Matchings II: Minimum Cost Flow.
Slides:PPTX, PDF.
Graph Isomorphism.
Slides: PPTX, PDF.
Fixed Parameter Tractability I.
Slides: PPTX, PDF.
Further reading:
  • Cygan et al.: Sections 2.1, 2.2, 2.5, 3.1, 3.5, 5.2.
51
December 19th
First Exam.
Topics for the exam are the topics of weeks 46-49 and the Tuesday lecture of week 50.
December 21st
Fixed Parameter Tractability I.
Slides: PPTX, PDF.
Further reading:
  • Cygan et al.: Sections 2.1, 2.2, 2.5, 3.1, 3.5, 5.2.
2
January 9rd
Introduction to Approximation Algorithms
Slides: PPTX, PDF (first part).
Further reading:
  • Cormen et al.: Chapter 35.
  • Kleinberg and Tardos: Chapter 12.
January 11th
Fixed Parameter Tractability II.
Slides: PPTX, PDF.
Note: some parts of the presentation / material were not covered in the course 2017/18, and are this year not part of the course (and there will be no questions on this material in the exams):
  • The correctness proof of the Nemhauser/Trotter reduction for Vertex Cover
  • Iterative compression
  • Color Coding

Further reading:
  • Cygan et al.: Sections 2.1, 2.2, 2.5, 3.1, 3.5, 5.2.
3
January 16th
The Landscape of Approximation Algorithms.
Slides: PPTX, PDF (third part)
Further reading:
  • Cormen et al.: Chapter 35.
  • Kleinberg and Tardos: Chapter 12.
  • Ausiello et al.: Chapter 3.(download)
January 18nd
Treewidth I.
Slides: PPTX, PDF.
Further reading:
  • Cygan et al.: Sections 7.1, 7.2, 7.3.
Shortest Paths and Treewidth
Slides: T.B.A.
4
January 23rd
Approximation Complexity.
Slides: PPTX, PDF (fourth and fifth parts).
Further reading:
January 25th
Treewidth
Slides: PPT, PDF.
Shapley values and treewidth.
Slides: PPTX, PDF.
5
Februari 1st
Second Exam.
Topics for the exam are the topics of weeks 51 - 4.