- 2014 Spring/Summer (Jan - May)
Tentative topic lists:
1. Introduction and Methodology: P vs NP, NP Optimization problems, Approximation Ratio
2. Techniques: Greedy and combinatorial methods Local search, Dynamic programming and approximation schemes, Linear programming rounding methods (primal-dual, dual-fitting, iterated rounding).
3. Problems: Metric-TSP, knapsack, bin packing, multiprocessor scheduling, Steiner trees, Steiner forests, vertex cover, set cover and generalizations, k-center, k-median, facility location, max cut, multiway cut, k-cut, multicut, art gallery, closest pair, other geometric problems.
Books to be followed in the course:
1. The Design of Approximation Algorithms by David Williamson and David Shmoys, Cambridge University Press, 2011.
2. Approximation Algorithms by Vijay Vazirani, Springer-Verlag, 2004.
3. Geometric Approximation Algorithms by Sariel Har-Peled, American Mathematical Society, 2011.