- 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,
STOC*Lower Stretch Spanning Trees,*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.
- 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

- 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