Chawla, Shuchi, Gupta, Anupam and Raecke, Harald. (2008) Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. ACM Transactions on Algorithms , Vol.4 (No.2). ISSN 1549-6325

Full text not available from this repository.

Abstract

In this article, we study metrics of negative type, which are metrics ( V, d) such that root d is an Euclidean metric; these metrics are thus also known as l(2)-squared metrics. We show how to embed n-point negative-type metrics into Euclidean space l(2) with distortion D = O(log (3/4) n). This embedding result, in turn, implies an O(log (3/4) k)-approximation algorithm for the Sparsest Cut problem with nonuniform demands. Another corollary we obtain is that n-point subsets of l(1) embed into l(2) with distortion O(log (3/4) n).

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH):	Approximation algorithms, Metric spaces, Embeddings (Mathematics), Graph theory -- Data processing
Journal or Publication Title:	ACM Transactions on Algorithms
Publisher:	Association for Computing Machinery, Inc.
ISSN:	1549-6325
Date:	May 2008
Volume:	Vol.4
Number:	No.2
Number of Pages:	18
Identification Number:	10.1145/1361192.1361199
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Funder:	National Science Foundation (U.S.) (NSF), Alfred P. Sloan Foundation
Grant number:	CCR-0122581 (NSF), CCF-0448095 (NSF)
Version or Related Resource:	Extended version of the paper presented at 16th Annual ACM/SIAM Symposium on Discrete Algorithms, Vancouver, Canada, Jan 23-25, 2005
Type of Event:	Other
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.
URI:	http://wrap.warwick.ac.uk/id/eprint/28016

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item