[1]   Sanjeev Arora, Satish Rao, and Umesh V. Vazirani: Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2):1–37, 2009. [doi:10.1145/1502793.1502794]

[2]   Patrice Assouad: Sur la distance de Nagata. C. R. Acad. Sci. Paris Ser. I Math., 1(294):31–34, 1982.

[3]   Baruch Awerbuch and David Peleg: Sparse partitions. In Proc. 31st FOCS, pp. 503–513. IEEE Comp. Soc. Press, 1990. [doi:10.1109/FSCS.1990.89571]

[4]   Yair Bartal: Probabilistic approximation of metric spaces and its algorithmic applications. In Proc. 37th FOCS, pp. 184–193. IEEE Comp. Soc. Press, 1996. [doi:10.1109/SFCS.1996.548477]

[5]   Yair Bartal and Robert Krauthgamer: Unpublished, 2007.

[6]    Mihai Bǎdoiu, Piotr Indyk, and Anastasios Sidiropoulos: Approximation algorithms for embedding general metrics into trees. In Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms (SODA’07), pp. 512–521. Society for Industrial and Applied Mathematics, 2007.

[7]   Gruia Calinescu, Howard J. Karloff, and Yuval Rabani: An improved approximation algorithm for Multiway Cut. J. Comput. System Sci., 60(3):564–574, 2000. [doi:10.1006/jcss.1999.1687]

[8]   Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, and Serge Plotkin: Approximating a finite metric by a small number of tree metrics. In Proc. 39th FOCS, pp. 379–388. IEEE Comp. Soc. Press, 1998. [doi:10.1109/SFCS.1998.743488]

[9]    Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, and Mihalis Yannakakis: The complexity of multiterminal cuts. SIAM J. Comput., 23(4):864–894, 1994. [doi:10.1137/S0097539792225297]

[10]   Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci., 69(3):485–497, 2004. [doi:10.1016/j.jcss.2004.04.011]

[11]   Jittat Fakcharoenphol and Kunal Talwar: Improved decompositions of graphs with forbidden minors. In Proc. 6th Intern. Workshop Approx. Algorithms for Comb. Opt. (APPROX ’03), volume 2764 of Lecture Notes in Comput. Sci., pp. 871–882. Springer, 2003. [doi:10.1007/978-3-540-45198-3_4]

[12]   Uriel Feige: A threshold of lnn for approximating set cover. J. ACM, 45(4):634–652, 1998. [doi:10.1145/285055.285059]

[13]   Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis: Approximate max-flow min-(multi)cut theorems and their applications. SIAM J. Comput., 25(2):235–251, 1996. [doi:10.1137/S0097539793243016]

[14]   Anupam Gupta, Robert Krauthgamer, and James R. Lee: Bounded geometries, fractals, and low-distortion embeddings. In Proc. 44th FOCS, pp. 534–543. IEEE Comp. Soc. Press, 2003. [doi:10.1109/SFCS.2003.1238226]

[15]   James D. Guyton and Michael F. Schwartz: Locating nearby copies of replicated internet servers. In Proc. Conf. Appl., Technol., Architectures, and Protocols for Comput. Commun. (SIGCOMM ’95), pp. 288–298, New York, NY, USA, 1995. ACM Press. [doi:10.1145/217382.217463]

[16]   Elad Hazan, Shmuel Safra, and Oded Schwartz: On the complexity of approximating k-set packing. Comput. Complexity, 15(1):20–39, 2006. [doi:10.1007/s00037-006-0205-6]

[17]   Claire Kenyon, Yuval Rabani, and Alistair Sinclair: Low distortion maps between point sets. SIAM J. Comput., 39(4):1617–1636, 2009. [doi:10.1137/080712921]

[18]   Philip N. Klein, Serge A. Plotkin, and Satish Rao: Excluded minors, network decomposition, and multicommodity flow. In Proc. 25th STOC, pp. 682–690. ACM Press, May 1993. [doi:10.1145/167088.167261]

[19]   Jon M. Kleinberg, Aleksandrs Slivkins, and Tom Wexler: Triangulation and embedding using small sets of beacons. J. ACM, 56(6):1–37, 2009. Earlier version in FOCS ’04, pp. 444–453. [doi:10.1145/1568318.1568322]

[20]   Jon M. Kleinberg and Éva Tardos: Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields. J. ACM, 49(5):616–639, 2002. [doi:10.1145/585265.585268]

[21]   Robert Krauthgamer: On triangulation of simple networks. In Proc. 19th Ann. ACM Symp. Parallel Algorithms and Architectures (SPAA’07), pp. 8–15. ACM Press, 2007. [doi:10.1145/1248377.1248380]

[22]   Robert Krauthgamer and James R. Lee: Algorithms on negatively curved spaces. In Proc. 47th FOCS, pp. 119–132. IEEE Comp. Soc. Press, 2006. [doi:10.1109/FOCS.2006.9]

[23]   Robert Krauthgamer, James R. Lee, Manor Mendel, and Assaf Naor: Measured descent: A new embedding method for finite metrics. Geom. Funct. Anal., 15(4):839–858, 2005. [doi:10.1007/s00039-005-0527-6]

[24]   Robert Krauthgamer and Tim Roughgarden: Metric clustering via consistent labeling. In Proc. 19th Ann. ACM-SIAM Symp. Discrete Algorithms (SODA’08), pp. 809–818, 2008.

[25]   Urs Lang and Thilo Schlichenmaier: Nagata dimension, quasisymmetric embeddings, and Lipschitz extensions. Int. Math. Res. Not., 2005(58):3625–3655, 2005. [doi:10.1155/IMRN.2005.3625]

[26]   Michael Langberg, Yuval Rabani, and Chaitanya Swamy: Approximation algorithms for graph homomorphism problems. In Proc. 9th Intern.. Workshop Approx. Algorithms for Comb. Opt. (APRROX ’06), volume 4110 of Lecture Notes in Comput. Sci., pp. 176–187. Springer, 2006. [doi:10.1007/11830924_18]

[27]   James R. Lee and Assaf Naor: Metric decomposition, smooth measures, and clustering. Manuscript, available at http://www.cims.nyu.edu/~naor/homepage\%20files/cluster.pdf, 2004.

[28]   James R. Lee and Anastasios Sidiropoulos: Genus and the geometry of the cut graph. In Proc. 20th Ann. ACM-SIAM Symp. Discrete Algorithms (SODA ‘10), pp. 193–201. SIAM, 2010.

[29]   Frank Thomson Leighton and Satish Rao: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In Proc. 29th FOCS, pp. 422–431. IEEE Comp. Soc. Press, 1988. [doi:10.1109/SFCS.1988.21958]

[30]   Nathan Linial, Eran London, and Yuri Rabinovich: The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215–245, 1995. [doi:10.1007/BF01200757]

[31]   Nathan Linial and Michael Saks: Low diameter graph decompositions. Combinatorica, 13(4):441–454, 1993. [doi:10.1007/BF01303516]

[32]   Carsten Lund and Mihalis Yannakakis: On the hardness of approximating minimization problems. J. ACM, 41(5):960–981, 1994. [doi:10.1145/185675.306789]

[33]   Jiří Matoušek and Anastasios Sidiropoulos: Inapproximability for metric embeddings into R^d. In Proc. 49th FOCS, pp. 405–413. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.21]

[34]   Rajeev Motwani and Prabhakar Raghavan: Randomized Algorithms. Cambridge University Press, 1995.

[35]   Satish Rao: Small distortion and volume preserving embeddings for planar and Euclidean metrics. In Proc. 15th Ann. Symp. Comput. Geom. (SoCG ‘99), pp. 300–306. ACM Press, 1999. [doi:10.1145/304893.304983]

[36]   Ran Raz and Shmuel Safra: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proc. 29th STOC, pp. 475–484. ACM Press, 1997. [doi:10.1145/258533.258641]

[37]   Aleksandrs Slivkins: Distributed approaches to triangulation and embedding. In Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms (SODA’05), pp. 640–649, 2005.

[38]   Aleksandrs Slivkins: Distance estimation and object location via rings of neighbors. Distrib. Comput., 19(4):313–333, 2007. Earlier version in PODC ’05, pp. 41–50. [doi:10.1007/s00446-006-0015-8]