References: |
ARORA, S., LEE, J., AND NAOR, A. 2005. Euclidean distortion and the sparsest cut. In Proceedings of the 37th ACM Symposium on Theory of Computing (STOC). ACM Press, New York, NY, 553–562. ARORA, S., RAO, S., AND VAZIRANI, U. 2004. Expander flows, geometric embeddings, and graph partitionings. In Proceedings of the 36th ACM Symposium on Theory of Computing (STOC). ACM Press, New York, NY, 222–231. AUMANN, Y. AND RABANI, Y. 1998. An O( log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput. 27, 1, 291–301. BARTAL, Y. 1998. On approximating arbitrary metrics by tree metrics. In Proceedings of the 30th ACM Symposium on Theory of Computing (STOC). ACM Press, New York, NY, 161–168. BOURGAIN, J. 1985. On Lipschitz embeddings of finite metric spaces in Hilbert space. Israel J. Math. 52, 1-2, 46–52. C˘ALINESCU, G., KARLOFF, H. J., AND RABANI, Y. 2004. Approximation algorithms for the 0-extension problem. SIAM J. Comput. 34, 2, 358–372. CHAWLA, S., KRAUTHGAMER, R., KUMAR, R., RABANI, Y., AND SIVAKUMAR, D. 2006. On the hardness of approximating sparsest cut and multicut. Computat. Complex. 15, 2, 94–114. CHEKURI, C., GUPTA, A., NEWMAN, I., RABINOVICH, Y., AND SINCLAIR, A. 2006. Embedding kouterplanar graphs into l1. SIAM J. Discrete Math. 20, 1, 119–136. CLARKSON, K. L. 1995. Las Vegas algorithms for linear and integer programming when the dimension is small. J. ACM 42, 2, 488–499. DEZA, M. M. AND LAURENT, M. 1997. Geometry of Cuts and Metrics. Algorithms and Combinatorics, vol. 15. Springer-Verlag, Berlin, Germany. ENFLO, P. 1969. On the nonexistence of uniform homeomorphisms between L p-spaces. Arkiv F¨or Matematik 8, 103–105. FAKCHAROENPHOL, J.,RAO, S., AND TALWAR,K. 2004. Atight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69, 3, 485–497. GOEMANS,M. X. 1997. Semidefinite programming and combinatorial optimization. Math. Program. 49, 143–161. GUPTA, A., KRAUTHGAMER, R., AND LEE, J. R. 2003. Bounded geometries, fractals, and low–distortion embeddings. In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 534–543. GUPTA, A., NEWMAN, I., RABINOVICH, Y., AND SINCLAIR, A. 2004. Cuts, trees and �1-embeddings of graphs. Combinatorica 24, 2, 233–269. INDYK, P. 2001. Algorithmic aspects of geometric embeddings. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 10–33. KARZANOV, A. V. 1985. Metrics and undirected cuts. Math. Program. 32, 2, 183–198. KHOT, S. 2002. On the power of unique 2-prover 1-round games. In Proceedings of the 34th ACM Symposium on Theory of Computing (STOC). ACM Press, New York, NY, 767–775. KHOT, S. AND VISHNOI, N. 2005. The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into �1. In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 53–62. KRAUTHGAMER, R., LEE, J., MENDEL, M., AND NAOR, A. 2005. Measured descent: A new embedding method for finite metrics. Geom. Funct. Anal. 15, 4, 839–858. KRAUTHGAMER, R. AND RABANI, Y. 2006. Improved lower bounds for embeddings into �1. In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM Press, New York, NY, 1010–1017. LEE, J. R. 2005. On distance scales, embeddings, and efficient relaxations of the cut cone. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACMPress, New York, NY, 92–101. LEE, J. R. AND NAOR, A. 2005. Extending lipschitz functions via random metric partitions. Inventiones Mathematicae 160, 1, 59–95. LEIGHTON, F. T. AND RAO, S. B. 1999. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46, 6, 787–832. LINIAL, N. 2002. Finite metric-spaces – combinatorics, geometry and algorithms. In Proceedings of the International Congress of Mathematicians Vol. III. Higher Education Press, Beijing, China, 573–586. LINIAL, N., LONDON, E., AND RABINOVICH, Y. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 2, 215–245. LITTLESTONE,N. ANDWARMUTH,M.K. 1994. The weighted majority algorithm. Inform. Comput. 108, 2, 212–261. MATOUˇSEK, J. 1999. On embedding trees into uniformly convex Banach spaces. Israel J. Math. 114, 221–237. MATOUˇSEK, J. 2002. Lectures on discrete geometry. Graduate Texts in Mathematics, vol. 212. Springer, Berlin, Germany. MATOUˇSEK, J. 1996. On the distortion required for embedding finite metric spaces into normed spaces. Israel J. Math. 93, 333–344. RABINOVICH, Y. 2003. On average distortion of embedding metrics into the line and into �1. In Proceedings of the 35th ACM Symposium on Theory of Computing (STOC). ACM Press, New York, NY, 456–462. RAO, S. B. 1999. Small distortion and volume preserving embeddings for planar and Euclidean metrics. In Proceedings of the 15th ACM Symposium on Computational Geometry. ACM Press, New York, NY, 300–306. SHAHROKHI, F. AND MATULA, D. W. 1990. The maximum concurrent flow problem. J. ACM 37, 2, 318–334. SHMOYS, D. B. 1997. Cut problems and their application to divide-and-conquer. In Approximation Algorithms for NP-hard Problems, D. S. Hochbaum, Ed. PWS Publishing, Boston, MA, 192–235. WELZL, E. 1996. Suchen und Konstruieren durch Verdoppeln. In Highlights der Informatik, I.Wegener, Ed. Springer, Berlin, Germany, 221–228. |