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

DOI10.1090/S0002-9947-2010-05186-4zbMath1219.68106MaRDI QIDQ3065742

Anastasios Sidiropoulos, Ji{ří} Matoušek

Publication date: 6 January 2011

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

zbMATH Keywords

metric spaceNP-hardnesslow-distortion embedding

Mathematics Subject Classification ID

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

Related Items (4)

Filament plots for data visualization ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Lipschitz embedding of finite metric spaces in Hilbert space
• The geometry of graphs and some of its algorithmic applications
• Plane embeddings of planar graph metrics
• Embedding tree metrics into low dimensional Euclidean spaces
• Local Global Tradeoffs in Metric Embeddings
• Extensions of Lipschitz mappings into a Hilbert space
• Low distortion maps between point sets
• Low-distortion embeddings of general metrics into the line
• Local versus global properties of metric spaces
• Total Ordering Problem
• A Geometric Approach to Betweenness
• New Foundation of Euclidean Geometry
• Low-Distortion Embeddings of Trees
• Über die zusammenziehende und Lipschitzsche Transformationen
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Trees and Markov convexity
• Geometry of cuts and metrics

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