Schedule

• Tuesday May 7th, from 15:00 to 17:00, Room B3
• Wednesday May 8th, from 9:00 to 11:00, Room C2
• Wednesday May 15th, from 9:00 to 11:00, Room C2
• Wednesday May 15th, from 14:00 to 16:00, Room I2
• Wednesday May 22nd, from 9:00 to 11:00, Room "Verde"
• Wednesday May 22nd, from 16:00 to 18:00, Room I2

Lecture Notes

• Lecture 1: Introduction
• Lecture 2: The set cover problem [1, chapter 1]
• Lecture 3: Greedy algorithms and local search [1, chapter 2] and [2, chapter 2.1]
• Lecture 4: Rounding data and dynamic programming [1, chapter 3]
• Lecture 5: Deterministic rounding of linear programs [1, chapter 4]
• Lecture 6: The primal-dual method [1, chapter 7]
• Lecture 7: Techniques in proving the hardness of approximation [1, chapter 16]

Seminars

• Proposed Seminars

Lectures by date

• May-07-2013: Introduction; The set cover problem
• May-08-2013: The set cover problem
• May-15-2013, 9:00-11:00: Greedy algorithms and local search
• May-15-2013, 14:00-16:00: Rounding data and dynamic programming
• May-22-2013, 9:00-11:00: Deterministic rounding of linear programs
• May-22-2013, 16:00-18:00: The primal-dual method; Techniques in proving the hardness of approximation

Textbooks

Most of the course is based on [1]

• [1] The Design of Approximation Algorithms
  David P. Williamson and David B. Shmoys
  Cambridge University Press, 2011.
• [2] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi
  Complexity And Approximation
  Combinatorial Optimization Problems And Their Approximability Properties
  Springer, 1999.
• [3] V. Vazirani
  Approximation Algorithms
  Springer, 2003.
• [4] Approximation Algorithms for NP-Hard Problems
  Dorit S. Hochbaum
  PWS Publishing Company, 1995.