Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces

DOI10.1137/17M1113527zbMath1417.68289OpenAlexW2920873618WikidataQ128246675 ScholiaQ128246675MaRDI QIDQ3119488

R. Ravi, Anastasios Sidiropoulos, Anupam Gupta, Kedar Dhamdhere, Harald Räcke, Mihai Bădoiu, Yuri Rabinovich, Piotr Indyk

Publication date: 12 March 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/17m1113527

zbMATH Keywords

spheredistortionlineapproximation algorithmsmetric embeddings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Lipschitz embedding of finite metric spaces in Hilbert space
• On some geometric optimization problems in layered manufacturing
• Kirszbraun's theorem and metric spaces of bounded curvature
• Approximating the bandwidth via volume respecting embeddings
• Absolute Lipschitz extendability
• The geometry of graphs and some of its algorithmic applications
• On the distortion required for embedding finite metric spaces into normed spaces
• The analysis of proximities: Multidimensional scaling with an unknown distance function: I, II
• Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis
• Nonmetric multidimensional scaling. A numerical method
• Distortion is Fixed Parameter Tractable
• Combinatorial theorems about embedding trees on the real line
• Inapproximability for metric embeddings into $\mathbb{R}^{d}$
• Low-distortion embeddings of general metrics into the line
• Low Distortion Maps Between Point Sets
• Hardness of Embedding Metric Spaces of Equal Size
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)
• Über die zusammenziehende und Lipschitzsche Transformationen
• A robust model for finding optimal evolutionary trees
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Slightly Superexponential Parameterized Problems
• An Exact Algorithm for Minimum Distortion Embedding
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler

This page was built for publication: Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces