Inapproximability for metric embeddings into \mathbb{R}^{d}

DOI10.1090/S0002-9947-2010-05186-4MaRDI QIDQ3065742zbMATH OpenFDO

Authors Anastasios Sidiropoulos, Jiří Matoušek

Publication date 6 January 2011

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1090/S0002-9947-2010-05186-4

zbMATH Keywords

low-distortion embeddingmetric spaceNP-hardness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On embedding expanders into \(\ell_p\) spaces
• scientific article; zbMATH DE number 64771
• Advances in metric embedding theory
• Hardness of Embedding Metric Spaces of Equal Size
• Inapproximability for planar embedding problems
• On the 3-distortion of a path
• Ultra-low-dimensional embeddings for doubling metrics
• Local global tradeoffs in metric embeddings
• On the Optimality of Gluing over Scales
• On the optimality of gluing over scales

Cites work

• A Geometric Approach to Betweenness
• Approximation algorithms for embedding general metrics into trees
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Circular partitions with applications to visualization and embeddings
• Embedding tree metrics into low dimensional Euclidean spaces
• Extensions of Lipschitz mappings into a Hilbert space
• Geometry of cuts and metrics
• scientific article; zbMATH DE number 4169644 (Why is no real title available?)
• scientific article; zbMATH DE number 5506208 (Why is no real title available?)
• scientific article; zbMATH DE number 4102053 (Why is no real title available?)
• Local global tradeoffs in metric embeddings
• Local versus global properties of metric spaces
• Low distortion maps between point sets
• Low-distortion embeddings of general metrics into the line
• Low-Distortion Embeddings of Trees
• New Foundation of Euclidean Geometry
• On Lipschitz embedding of finite metric spaces in Hilbert space
• Plane embeddings of planar graph metrics
• The complexity of low-distortion embeddings between point sets
• The geometry of graphs and some of its algorithmic applications
• Total Ordering Problem
• Trees and Markov convexity
• Über die zusammenziehende und Lipschitzsche Transformationen

Cited in

(14)

• Filament plots for data visualization
• Metric Spaces Admitting Low-distortion Embeddings into All n-dimensional Banach Spaces
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• Hardness of Embedding Metric Spaces of Equal Size
• PLANE WITH $A_{\infty}$ -WEIGHTED METRIC NOT BILIPSCHITZ EMBEDDABLE TO ${\bb R}^n$
• scientific article; zbMATH DE number 2079367 (Why is no real title available?)
• scientific article; zbMATH DE number 2079382 (Why is no real title available?)
• Algorithms for metric learning via contrastive embeddings
• Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
• Inapproximability for planar embedding problems
• Paper Retraction: On the Hardness of Embeddings Between Two Finite Metrics
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Automata, Languages and Programming
• A hardness of approximation result in metric geometry

This page was built for publication: Inapproximability for metric embeddings into $\mathbb{R}^{d}$

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