Site menu:

Lecture notes

Lecture 23: sublinear algorithm [slides].
Lecture 22: probabilistic method [slides].
Lecture 21: randomized algorithms and randomized rounding [slides].

Reference:
  • A survey on randomized rounding [pdf] by Srinivasan.
Lecture 20: introduction to randomized algorithms [slides].
Lecture 19: approximation algorithms: semidefinite programming [slides].

Reference:
  • Handouts distributed in class.
  • A survey on "semidefinite programming in combinatorial optimization" [ps] by Lovász. (highly recommended)
  • An exposition of the rubber band method" [ps] by Lovász. (class demo)
Lecture 18: approximation algorithms: multicut [slides].

Reference:
  • Handouts distributed in class.
  • A survey of graph cut problems [ps] by Shmoys. (See Section 5.3.2 for a reduction from sparsest cut to multicut.)
Lecture 17: approximation algorithms: graph paritioning problems [slides].

Reference:
  • Handouts on multiway cut distributed in lecture 13.
Lecture 16: approximation algorithms: job scheduling [slides].

Reference:
  • Handouts distributed in class.
Lecture 15: approximation algorithms: iterative rounding [slides].

Reference:
  • The 2-approximation algorithm on survivable network design [ps] by Jain.
Lecture 14: approximation algorithms: dynamic programming [slides].

Reference:
  • Handouts distributed in class.
Lecture 13: approximation algorithms: combinatorial approaches [slides].

Reference:
  • Handouts distributed in class.
Lecture 12: introduction to approximation algorithms [slides].
Lecture 11: totally unimodular matrices, simplex algorithm, and ellipsoid algorithm [slides].

Reference:
  • Notes on totally unimodular matrices [ps] by Schrijver.
  • Notes on the simplex algorithm [pdf] and [pdf] by Magen.
  • Notes on the ellipsoid algorithm [ps] by Goemans.
Lecture 10: linear programming duality [slides].

Reference:
  • Notes on linear programming [ps] by Schrijver.
Lecture 9: general matching polytopes [slides].
Lecture 8: bipartite matching and stable matching polytopes [slides].

Supplementary material:
  • Notes on vertex (or basic) solutions [pdf] (only page 1-3) by Karger.
Lecture 7: introduction to linear and integer programming [slides].
Lecture 6: graph orientations and submodular flows [slides]

Supplementary material:
  • A proof of Menger's theorem by minimal counterexample [ps|pdf].
  • Submodular functions in combinatorial optimization [ps|pdf].
Lecture 5: minimum cost flows [slides].
Lecture 4: maximum flows and applications [slides], [animation] by Wayne.

References:
Lecture 3: matchings [slides]

Supplementary material:
Lecture 2: stable matchings [ps|pdf], bipartite matchings [ps|pdf].

Additional reading (optional):
Lecture 1: introduction. See the course information page and the course project page.