Small distortion and volume preserving embeddings for planar and Euclidean metrics

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Small distortion and volume preserving embeddings for planar and Euclidean metrics

Full text

Pdf (723 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the fifteenth annual symposium on Computational geometry table of contents

Miami Beach, Florida, United States

Pages: 300 - 306

Year of Publication: 1999

ISBN:1-58113-068-6

Author

Satish Rao

NEC Research Institute, 4 Independence Way, Princeton, NJ

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 104, Citation Count: 31

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/304893.304983 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998 [doi>10.1137/S0097539794285983]
	2	J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math, 52:46-52, 1985.
	3	P. Frankl , H. Maehara, The Johnson-Lindenstrauss Lemma and the sphericity of some graphs, Journal of Combinatorial Theory Series A, v.44 n.3, p.355-362, June 1987
	4	U. Feige. Improved volume respecting embeddings.
	5	Uriel Feige, Approximating the bandwidth via volume respecting embeddings (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.90-99, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276716]
	6	A. Frank. Packing paths, circuits and cuts- a survey. In B. Korte, L. Lov#z, H.J. PrSmel, and A. Schrijver, editors, Paths, Flows, and VLSI- Layout, pages 47-100. Springer-Verlag, Berlin, 1990.
	7	Richard M. Karp, Frank Thomson Leighton, Ronald L. Rivest, C. D. Thompson, Umesh V. Vazirani, and Vijay V. Vazirani. Global wire routing in two-dimensionalaxrays. In Proceedings of the 24th Annual Symposium on Foundations of Computer Science, pages 453-459, 1983.
	8	Philip Klein , Serge A. Plotkin , Satish Rao, Excluded minors, network decomposition, and multicommodity flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.682-690, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167261]
	9	N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15:215-245, 1995.
	10	Santosh Vempala. Approximating vlsi layout problems. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998.

CITED BY 31

	Ilan Newman , Yuri Rabinovich, A lower bound on the distortion of embedding planar metrics into Euclidean space, Proceedings of the eighteenth annual symposium on Computational geometry, p.94-96, June 05-07, 2002, Barcelona, Spain
	Nathan Linial , Avner Magen , Assaf Naor, Girth and euclidean distortion, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Anupam Gupta, Improved bandwidth approximation for trees, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.788-793, January 09-11, 2000, San Francisco, California, United States
	Yuri Rabinovich, On average distortion of embedding metrics into the line and into L₁, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	James R. Lee, On distance scales, embeddings, and efficient relaxations of the cut cone, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Chandra Chekuri , Sanjeev Khanna , F. Bruce Shepherd, The all-or-nothing multicommodity flow problem, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Sanjeev Arora , James R. Lee , Assaf Naor, Euclidean distortion and the sparsest cut, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Journal of Computer and System Sciences, v.69 n.3, p.485-497, November 2004
	Robert Krauthgamer , James R. Lee, The intrinsic dimensionality of graphs, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Mohammad T. Hajiaghayi , Robert Kleinberg , Tom Leighton, Improved lower and upper bounds for universal TSP in planar metrics, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.649-658, January 22-26, 2006, Miami, Florida
	Shuchi Chawla , Anupam Gupta , Harald Räcke, Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Uriel Feige , MohammadTaghi Hajiaghayi , James R. Lee, Improved approximation algorithms for minimum-weight vertex separators, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Bo Brinkman , Moses Charikar, On the impossibility of dimension reduction in l₁, Journal of the ACM (JACM), v.52 n.5, p.766-788, September 2005
	Adam Kalai , Santosh Vempala, Efficient algorithms for online decision problems, Journal of Computer and System Sciences, v.71 n.3, p.291-307, October 2005
	MohammadHossein Bateni , MohammadTaghi Hajiaghayi , Erik D. Demaine , Mohammad Moharrami, Plane embeddings of planar graph metrics, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	James R. Lee , Manor Mendel , Assaf Naor, Metric structures in L1: dimension, snowflakes, and average distortion, European Journal of Combinatorics, v.26 n.8, p.1180-1190, November 2005
	Chandra Chekuri , Anupam Gupta , Ilan Newman , Yuri Rabinovich , Alistair Sinclair, Embedding k-outerplanar graphs into ℓ1, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Chandra Chekuri , Sanjeev Khanna , F. Bruce Shepherd, Edge-disjoint paths in Planar graphs with constant congestion, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Ittai Abraham , Yair Bartal , Ofer Neimany, Advances in metric embedding theory, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	James R. Lee, Volume distortion for subsets of Euclidean spaces: extended abstract, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Bo Brinkman , Adriana Karagiozova , James R. Lee, Vertex cuts, random walks, and dimension reduction in series-parallel graphs, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Shuchi Chawla , Anupam Gupta , Harald Räcke, Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut, ACM Transactions on Algorithms (TALG), v.4 n.2, p.1-18, May 2008
	T-H. Hubert Chan , Anupam Gupta , Kunal Talwar, Ultra-low-dimensional embeddings for doubling metrics, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.333-342, January 20-22, 2008, San Francisco, California
	Robert Krauthgamer , Tim Roughgarden, Metric clustering via consistent labeling, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.809-818, January 20-22, 2008, San Francisco, California
	Pierre Dehornoy, On the 3-distortion of a path, European Journal of Combinatorics, v.29 n.1, p.171-178, January, 2008
	Stefan Funke , Nikola Milosavljevic, Network sketching or: "How Much Geometry Hides in Connectivity?--Part II", Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.958-967, January 07-09, 2007, New Orleans, Louisiana
	Ittai Abraham , Yair Bartal , Ofer Neiman, Embedding metric spaces in their intrinsic dimension, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.363-372, January 20-22, 2008, San Francisco, California
	Ittai Abraham , Yair Bartal , Ofer Neiman, On low dimensional local embeddings, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.875-884, January 04-06, 2009, New York, New York
	Glencora Borradaile , James R. Lee , Anastasios Sidiropoulos, Randomly removing g handles at once, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	James R. Lee , Anastasios Sidiropoulos, On the geometry of graphs with a forbidden minor, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA