Authors: Piotr Indyk - IEEE Symposium on Foundations of Computer Science, FOCS 2001 cited by 258
The author surveys algorithmic results obtained using low-distortion embeddings of metric spaces into (mostly) normed spaces. He shows that low-distortion embeddings provide a powerful and versatile toolkit for solving algorithmic problems. Their fundamental nature makes them applicable in a variety of diverse settings, while their relation to rich mathematical fields (e.g., functional analysis) ensures availability of tools for their construction.
✨ Checking sign-in… PDF Cited by View BibTeX Hide BibTeX View BibTeX Cite
The dimension of almost spherical sections of… The dimension of almost spherical sections of convex bodies On lipschitz embedding of finite metric spaces… On lipschitz embedding of finite metric spaces in Hilbert space The Geometry of Graphs and Some of its… The Geometry of Graphs and Some of its Algorithmic Applications Probabilistic Approximations of Metri… Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications On Approximating Arbitrary Metrices by… On Approximating Arbitrary Metrices by Tree Metrics Approximating a Finite Metric by a Small Numbe… Approximating a Finite Metric by a Small Number of Tree Metrics Lower Bounds on the Distortion of Embedding… Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs Small Distortion and Volume Preserving… Small Distortion and Volume Preserving Embeddings for Planar and Euclidean Metrics Cuts, Trees and l1-Embeddings of Graphs Cuts, Trees and l1-Embeddings of Graphs An Algorithmic Theory of Learning: Robust… An Algorithmic Theory of Learning: Robust Concepts and Random Projection Approximating the Bandwidth via Volume… Approximating the Bandwidth via Volume Respecting Embeddings Lectures on discrete geometry Lectures on discrete geometry Finite metric spaces: combinatorics, geometry… Finite metric spaces: combinatorics, geometry and algorithms Low Stretch Spanning Trees Low Stretch Spanning Trees Graph Decomposition Lemmas and Their Role i… Graph Decomposition Lemmas and Their Role in Metric Embedding Methods Approximating Edit Distance Efficiently Approximating Edit Distance Efficiently Low-distortion embeddings of general… Low-distortion embeddings of general metrics into the line The complexity of low-distortion… The complexity of low-distortion embeddings between point sets Ramsey-type theorems for metric spaces with… Ramsey-type theorems for metric spaces with applications to online problems Embedding Metrics into Ultrametrics and Graphs… Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion A novel approach to embedding of metric… A novel approach to embedding of metric spaces (גישה חדשה לשיכונים של מרחבים מטריים.) On the geometry of graphs with a forbidden… On the geometry of graphs with a forbidden minor Geometric Approximation Algorithms Geometric Approximation Algorithms Clan Embeddings into Trees, and Low Treewidt… Clan Embeddings into Trees, and Low Treewidth Graphs Algorithmic Applications of Low-Distortion… Algorithmic Applications of Low-Distortion Geometric Embeddings Earlier references Focus paper Citing papers Older Newer Click a node to pin it, click the empty canvas to go back to this paper, or hover to preview. Open a node’s page from its title.
