General references

• Vijay Vazirani's book on Approximation Algorithms.
• Book on Approximation Algorithms edited by Dorit Hochbaum.
• David Williamson, Lecture Notes on Approximation Algorithms, 1998.
• Joseph Cheriyan and R. Ravi, Lecture notes on Approximation Algorithms for Network Problems, 1998.

Potential list of topics/lectures

Set Cover

• Chap 2.1, chap 13.1, 14.2, chap 15 of Vazirani.

TSP

• Chap. 3 in Vazirani
• Euclidean TSP. Chap 11 in Vazirani.
  Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems. Sanjeev Arora. Journal of the ACM 45(5) 753-782, 1998.
  Approximation schemes for NP-hard geometric optimization problems: A survey. Sanjeev Arora. This survey accompanied a semiplenary talk at ISMP and appeared in Math Programming, 97 (1,2) July 2003.
• H. Kaplan, M. Lewenstein, N. Shafrir and M. Sviridenko, "Approximation algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs", Journal of ACM v.52 (2005), pp. 602-626.

Primal-dual

• Multicut in trees. Chap 18 in Vazirani.
• Facility location. Chap 24 in Vazirani.
  ``Approximation Algorithms for Metric Facility Location and k-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation'', K. Jain and V. Vazirani, Journal of ACM, Vol. 48 (2001) 274-296.
• M.X. Goemans and D.P. Williamson, The Primal-Dual Method for Approximation Algorithms and its Application to Network Design Problems, in Approximation Algorithms, D. Hochbaum, Ed., 1997.
• How well can primal-dual and local-ratio algorithms perform?, A. Borodin, D. Cashman and A. Magen. ICALP 2005.

Bin Packing

• Chap. 9.
• Karmarkar and Karp, An efficient approximation scheme for the one-dimensional bin packing problem, FOCS 1982, 312--320.

MAXCUT and Semidefinite Programming

• Chap 26 of Vazirani.
• M.X. Goemans and D.P.Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming, J. ACM, 42, 1115--1145, 1995.
• Howard Karloff, How Good is the Goemans--Williamson MAX--CUT Algorithm?, SICOMP, Volume 29, pages 336--350, 1999.
• Uriel Feige and Gideon Schechtman. On the optimality of the random hyperplane rounding technique for MAX CUT. To appear in Random Structures and Algorithms.
• Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal Inapproximability Results for MAX-CUT and Other 2-variable CSPs? submitted to SIAM Journal on Computing.

Sparsest Cut

• David B. Shmoys, Cut problems and their application to divide-and-conquer, Chapter 5 of Approximation Algorithms, Dorit Hochbaum, editor.
• Expander Flows, Geometric Embeddings, and Graph Partitionings. Sanjeev Arora, Satish Rao, and Umesh Vazirani. ACM Symposium on Theory of Computing, 2004.
• Euclidean distortion and the sparsest cut. Sanjeev Arora, James Lee, and Assaf Naor. ACM Symposium on Theory of Computing, 2005.

Scheduling

• Packet routing and job-shop scheduling in O(congestion+dilation) steps, F. T. Leighton, Bruce M. Maggs, Satish B. Rao, Combinatorica, 1994, 167--186.

Steiner tree

• Sec 3.1 of Vazirani
• Gabriel Robins and Alexander Zelikovsky, Tighter Bounds for Graph Steiner Tree Approximation, SIDMA, Volume 19 pages 122--134, 2005.