Low-distortion embeddings of general metrics into the line
From MaRDI portal
Publication:3581393
DOI10.1145/1060590.1060624zbMath1192.68342OpenAlexW2163459114MaRDI QIDQ3581393
Mihai Bădoiu, Anastasios Sidiropoulos, Julia Chuzhoy, Piotr Indyk
Publication date: 16 August 2010
Published in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1060590.1060624
Related Items (26)
On the Minimum Eccentricity Shortest Path Problem ⋮ \(\ell ^2_2\) spreading metrics for vertex ordering problems ⋮ Filament plots for data visualization ⋮ On the minimum eccentricity shortest path problem ⋮ Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs ⋮ Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs ⋮ Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances ⋮ Unnamed Item ⋮ Optimal distortion embedding of complete binary trees into lines ⋮ The complexity of LSH feasibility ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs ⋮ Light Euclidean Spanners with Steiner Points ⋮ Combinatorial theorems about embedding trees on the real line ⋮ Toward a unified theory of sparse dimensionality reduction in Euclidean space ⋮ Line-distortion, bandwidth and path-length of a graph ⋮ An exact algorithm for minimum distortion embedding ⋮ Slightly Superexponential Parameterized Problems ⋮ Distortion lower bounds for line embeddings ⋮ On the graph turnpike problem ⋮ Inapproximability for metric embeddings into $\mathbb{R}^{d}$ ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Decomposing a graph into shortest paths with bounded eccentricity ⋮ Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces
This page was built for publication: Low-distortion embeddings of general metrics into the line
