On the optimality of gluing over scales

DOI10.1007/S00454-011-9359-3zbMATH Open1219.68159OpenAlexW2788840627MaRDI QIDQ635762FDOQ635762

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

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

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)

Cites Work

• Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\)
• The geometry of graphs and some of its algorithmic applications
• Measured descent: A new embedding method for finite metrics
• Expander graphs and their applications
• PLANE WITH $A_{\infty}$ -WEIGHTED METRIC NOT BILIPSCHITZ EMBEDDABLE TO ${\bb R}^n$
• Title not available (Why is that?)
• Bilipschitz embeddings of metric spaces into space forms
• Sharp uniform convexity and smoothness inequalities for trace norms
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
• Euclidean distortion and the sparsest cut
• A lower bound on the distortion of embedding planar metrics into Euclidean space
• On distance scales, embeddings, and efficient relaxations of the cut cone
• Volume distortion for subsets of Euclidean spaces
• On embedding expanders into \(\ell_p\) 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 impossibility of dimension reduction for doubling subsets of \(\ell_{p}\)
• On the Optimality of Gluing over Scales

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)