(Logo)   IMADA
University of Southern Denmark IMADA - Department of Mathematics and Computer Science

   

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.