On the optimality of gluing over scales

DOI10.1007/S00454-011-9359-3MaRDI QIDQ635762zbMATH OpenOpenAlexFDO

Authors Alexander Jaffe, James R. Lee, Mohammad Moharrami

Publication date 23 August 2011

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00454-011-9359-3

zbMATH Keywords

metric geometryfinite metric spacesEuclidean distortion

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• On the Optimality of Gluing over Scales
• Volume distortion for subsets of Euclidean spaces
• Advances in metric embedding theory
• Near-optimal distortion bounds for embedding doubling spaces into L ₁
• On distance scales, embeddings, and efficient relaxations of the cut cone

Cites work

• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• A lower bound on the distortion of embedding planar metrics into Euclidean space
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• Bilipschitz embeddings of metric spaces into space forms
• Embedding the diamond graph in L_p and dimension reduction in L₁
• Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
• Euclidean distortion and the sparsest cut
• Expander graphs and their applications
• Measured descent: A new embedding method for finite metrics
• On distance scales, embeddings, and efficient relaxations of the cut cone
• On embedding expanders into \(\ell_p\) spaces
• PLANE WITH $A_{\infty}$ -WEIGHTED METRIC NOT BILIPSCHITZ EMBEDDABLE TO ${\bb R}^n$
• Sharp uniform convexity and smoothness inequalities for trace norms
• The geometry of graphs and some of its algorithmic applications
• Volume distortion for subsets of Euclidean spaces

Cited in

(5)

• Metric Embedding via Shortest Path Decompositions
• Vertical perimeter versus horizontal perimeter
• Inapproximability for metric embeddings into $\mathbb{R}^{d}$
• On the Optimality of Gluing over Scales
• On the impossibility of dimension reduction for doubling subsets of \(\ell_{p}\)

This page was built for publication: On the optimality of gluing over scales

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q635762)