This short series of lectures deals with algorithmic techniques based on two well-know paradigms for designing approximation algorithms: the Primal-Dual Schema (PDS) and the Local-Ratio Technique (LRT).
The first lecture is an introduction to PDS and LRT. Each subsequent lecture covers a particular algorithmic technique related to the two paradigms. Even though each lecture will typically focus on one or two problem-specific results, we will always emphasize the underlying principles at work. It is worth noting that no previous knowledge on PDS or LRT will be assumed.
Below is a tentative schedule for the lectures. Any additional material and future updates will be posted in this space.
| Date | Topic | Relevant papers | Slides |
|---|---|---|---|
| Nov 29 | Intro to PDS and LRT and sketch of equivalence | [V Ch. 13] [BBFR] | ppt |
| Dec 13 | Randomized local ratio | [B] [ACN] | |
| Jan 17 | Lagrangian relaxation | [KPS] | ppt |
| Feb 7 | Dual fitting and factor revealing programs | [V Ch. 12] [IMM] | |
| Mar 6 | On-line primal-dual algorithms | [BJN] |