Abstract:
This is the first of a short series of lectures dealing with algorithmic techniques based on two well-know paradigms for designing approximation algorithms: the Primal-Dual Schema (PDS) and the Local-Ratio Technique (LRT).
We will begin with a gentle introduction to PDS and LRT. Each subsequent lecture will cover 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.
Link to a tentative list of topics :
http://www.mpi-inf.mpg.de/~jmestre/class/fall07/index.html