# Approximation Algorithms (Unipg)

# 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

# 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.