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.

Prerequisites

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)