Algorithmic applications of low-distortion geometric embeddings
- 1 January 2001
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15525244,p. 10-33
- https://doi.org/10.1109/sfcs.2001.959878
Abstract
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.Keywords
This publication has 57 references indexed in Scilit:
- Approximating the Bandwidth via Volume Respecting EmbeddingsJournal of Computer and System Sciences, 2000
- When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner TreeSIAM Journal on Computing, 2000
- A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning TreesSIAM Journal on Computing, 2000
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithmsJournal of the ACM, 1999
- The Fourth Moment MethodSIAM Journal on Computing, 1997
- Global self-organization of all known protein sequences reveals inherent biological signatures 1 1Edited by F. E. CohenJournal of Molecular Biology, 1997
- Self-organizing semantic mapsBiological Cybernetics, 1989
- The Johnson-Lindenstrauss lemma and the sphericity of some graphsJournal of Combinatorial Theory, Series B, 1988
- A Method for Simulating Stable Random VariablesJournal of the American Statistical Association, 1976
- Metric entropy of some classes of sets with differentiable boundariesJournal of Approximation Theory, 1974