A selection of topics for presentations:

Approximation algorithms:

• Facility Location Problem:
  
• Mohammad Mahdian, Yinyu Ye, and Jiawei Zhang, Approximation Algorithms for Metric Facility Location Problems, SIAM Journal on Computing 36 (2), 411-432, 2006.
• Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi, and Vijay Vazirani, Greedy Facility Location Algorithms Analyzed using Dual Fitting with Factor-Revealing LP, Journal of the ACM, 50 (6), pp. 795-824, November 2003.
• M. Sviridenko. An improved approximation algorithm for the metric uncapacitated facility location problem. In Proc. of the 9th Integer Programming and Combinatorial Optimization (IPCO), pages 240-257, 2002.
• F. A. Chudak and D. B. Shmoys. Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput., 33(1), pages 1-25, 2003.
• Jaroslaw Byrka. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. In Proceedings of APPROX 2007
• Approximation for high-connected subgraphs:
• G. Kortsarz and Z. Nutov, Approximating min-cost connectivity problems, Survey Chapter in handbook on approximation, 2006. For a pdf file
• J. Cheriyan, S. Vempala, and A. Vetta, An approximation algorithm for the minimum-cost k-vertex connected subgraph, SIAM J. Comput.) 32 (2003) pp.1050-1055, postscript
• J. Cheriyan and A. Vetta, Approximation Algorithms for Network Design with Metric Costs, to appear in SIDMA (SIAM J. Discr. Math.), postscript
• "Approximating the smallest k-edge connected spanning subgraph by LP-rounding", H.N. Gabow, M.X. Goemans, E. Tardos and D.P. Williamson, SODA 05, pp. 562-571. Complete version: postscript
• G. Kortsarz and Z. Nutov, Approximation Algorithms for k-node connected subgraphs, via critical graphs, SIAM journal on Computing, 35(1), 247-257, 2005. postscript

• Bounded degree subgraphs:
• M.X. Goemans, Minimum Bounded-Degree Spanning Trees, Proceedings of FOCS 2006, 273--282.
• Mohit Singh and Lap Chi Lau Approximating Minimum Bounded Degree Spanning Tress to within One of Optimal , Proceedings of STOC 2007.
• L.C. Lau, S. Naor, M. Salavatipour and M. Singh Survivable Network Design with Degree or Order Constraints, Proceedings of STOC 2007.
• Approximating metrics by tree metrics:
• N. Alon, R. Karp, D. Peleg, D. B. West, A graph-theoretic game and its application to the k-server problem, SICOMP 1995.
• Y. Bartal, Probabilistic Approximations of Metric Spaces and its Algorithmic Applications, FOCS 1996.
• J. Fakcharoenphol, S. Rao and K. Talwar, A tight bound on approximating arbitrary metrics by tree metrics. STOC 2003.
• M. Elkin, Y. Emek, D. Spielman, S. Teng, Lower Stretch Spanning Trees, STOC 2005.
• Sanjeev Arora: Polynomial time approximation schemes for Euclidean TSP and other Geometric Problems, ournal of the ACM 45(5) 753-782, 1998. [Postscript of journal version].
• Sanjeev Arora, Satish Rao, and Umesh Vazirani. Expander flows, geometric embeddings, and graph partitionings, STOC 2004
• k-Median Problem:
• M. Charikar, S. Guha, E. Tardos and D. Shmoys A Constant Factor Approximation for the K-Median Problem
• Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local Search Heuristics for k-median and Facility Location Problems. SIAM Journal of Computing 33(3), 2004 (conference version in STOC 2001).
• Uriel Feige, Robert Krauthgamer:  A polylogarithmic approximation of the minimum bisection. SIAM Journal on Computing, 31(4): 1090--1118 (2002).
• C. Chekuri, M. Charikar, T. Cheung, Z. Dai, A. Goel, S. Guha, and Ming Li, Approximation Algorithms for Directed Steiner Problems ,  in Journal of Algorithms, 1999, 33: 73-91.
• Naveen Garg, Goran Konjevod and R. Ravi, A polylogarithmic approximation algorithm for the group Steiner problem . special issue of Journal of Algorithms 37(1), (2000)
• Approximation algorithms for directed multicut:
• Joseph Cherian, Howard Karloff and Yuval Rabani, Approximating directed multicuts, Combinatorica 25(3) (2005) pp.251-269, postscript
• A. Gupta,  Improved Results for Directed Multicut. SODA 2003.
• A. Agarwal, N. Alon and M. Charikar, Improved Approximation for Directed Multicut and Directed Sparsest Cut, Proc. of the 39 ACM STOC, 671-680.
• Approximation algorithms for Buy-at-Bulk:
• B. Awerbuch and Y. Azar, Buy-at-bulk network design, FOCS 97.
  
• Adam Meyerson, Kamesh Munagala, and Serge Plotkin. Cost-Distance: Two-Metric Network Design. IEEE Symposium on Foundations of Computer Science (FOCS) 2000.
• C. Chekuri, S. Khanna, and S. Naor, A Deterministic Algorithm for the Cost-Distance Problem , short paper in SODA 2001.
• C. Chekuri, M. Hajiaghayi, G. Kortsarz, M.R. Salavatipour, Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design problems, In Proceedings of FOCS 2006.
• D. Karger, R. Motwani, M. Sudan, Approximate Graph Coloring by Semidefinite Programming, Journal of the ACM, 45(2): 246--265, March 1998. postscript

Hardness of approximation:

• Uriel Feige. A Threshold of ln n for Approximating Set Cover. Journal of the ACM, 45(4), 634--652, July 1998.
• Hardness of cost-distance and Buy-at-bulk network design:
• Matthew Andrews. Hardness of buy-at-bulk network design. FOCS '04.
• J. Chuzhoy, A. Gupta, S. Naor and A. Sinha.On the Approximability of Some Network Design Problems. ACM Transactions on Algorithms (TALG), SODA 2005 special issue
• Hardness of edge-disjoint paths:
• M. Andrews, J. Chuzhoy, S. Khanna and L. Zhang. Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion. In Proc. of FOCS 2005.
• Matthew Andrews, Lisa Zhang. Hardness of the undirected edge-disjoint paths problem. STOC '05.
• V. Guruswami, S. Khanna, R. Rajaraman, F.B. Shepherd, M. Yannakakis. Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems.
  JCSS, 67(3):473-496, 2003. (Preliminary version in Proc. of STOC 1999.)
• Hardness of congestion minimization:
• Matthew Andrews, Lisa Zhang. Logarithmic hardness of the directed congestion minimization problem. STOC '06.
• Matthew Andrews, Lisa Zhang. Hardness of the undirected congestion minimization problem. STOC '05.
• J. Chuzhoy, V. Guruswami, S. Khanna, and K. Talwar, Hardness of routing with congestion in directed graphs, STOC'07
  
• Hardness of Multi-cut and Sparsest cut:
• Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D. Sivakumar. On the hardness of approximating multicut and sparsest-cut. Invited to special issue of Computational Complexity. Preliminary version in Proc. of CCC 2005.
• J. Chuzhoy and S. Khanna. Polynomial Flow-Cut Gaps and Hardness of Directed Cut Problems In Proc. STOC 2007. Full version
  
• J. Chuzhoy and S. Khanna. Hardness of Cut Problems in Directed Graphs.  In Proc. of STOC 2006.
• Lower bound for group Steiner tree and directed Steiner tree:
• Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan and Nan Wang, Integrality ratio for group Steiner trees and Directed Steiner trees,
  SIAM Journal on Computing, 2007.
• Eran Halperin and Robi Krauthgamer, Polylogarithmic inapproximability, In Proceedings of STOC 2003.
• Irit Dinur, Venkatesan Guruswami, Subhash Khot, A new multilayered PCP and the hardness of hypergraph vertex cover, STOC 2003, to appear in SICOMP)
• Håstad result (warning: this is difficult):
• J. Håstad, Some optimal inapproximability results, Journal of ACM, Vol.~48, 2001, pp 798--859.
  
• The following course notes on this result might be useful: Lecture 16 (from a course by Venkatesan Guruswami and Ryan O'Donnell at University of Washington), Lecture 4, Lecture 5 (from a course by Subash Khot at Georgia Tech)
• Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, and Seffi Naor, Asymmetric k-center is log^*n-hard to Approximate JACM 2(4):538-551, 2005