DM833 - Approximation Algorithms

Spring 2014
Lene Monrad Favrholdt

Literature

Textbook:: Vijay V. Vazirani; Approximation Algorithms; Springer, 2003.

The current plan is to cover the following parts of the textbook:

Section 1.1: Introduction
Section 2.1: Set Cover
Chapter 3: Steiner Tree and TSP
Section 4.1: Multiway Cut
Section 5.1: k-Center
Chapter 8: Knapsack
Chapter 9: Bin Packing
Section 12.1 and 12.3: Introduction to LP-Duality
Chapter 13: Set Cover via Dual Fitting
Chapter 14: LP-Rounding Applied to Set Cover
Chapter 15: Set Cover via the Primal-Dual Schema
Chapter 24: Facility Location via the Primal-Dual Schema

The plan may change slightly during the course.