Yuval Rabani


67855 Discrete Optimization

Spring Semester, 2010

The course has two parts. In the first part we will discuss approximation algorithms for hard problems in combinatorial optimization, linear programming, and on-line computing. In the second part we will focus on algorithmic aspects of metric geometry, in particular related to approximation algorithms and on-line computing.

This is a graduate level course aimed at students with a strong inclination towards theory.


Students are expected to possess reasonable mathematical skills, and to master basic concepts and techniques in the theory of computation.

Lecture notes

Lecture 1: Introduction, greedy algorithms, local search, random solution (.pdf)

Lecture 2: Dual fitting, primal-dual algorithms, rounding (.pdf)

Lecture 3: Polynomial time approximation schemes (.pdf)

Lecture 4: The primal-dual schema and Lagrange relaxations (.pdf)

Lecture 5: Linear programming (.pdf)

Lecture 6: Randomized rounding (.pdf)

Lecture 7: On-line computing (.pdf)