Approximation Algorithms for Graph and Geometric Problems



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