Advances in metric embedding theory

DOI10.1016/j.aim.2011.08.003zbMath1250.46016MaRDI QIDQ5894374

Ofer Neiman, Yair Bartal, Ittai Abraham

Publication date: 2 December 2011

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aim.2011.08.003

zbMATH Keywords

dimension reduction; metric space; bilipschitz embedding

Mathematics Subject Classification ID

54E35: Metric spaces, metrizability

05C12: Distance in graphs

68W25: Approximation algorithms

46B85: Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science

Related Items

Volume in general metric spaces, Embeddability of snowflaked metrics with applications to the nonlinear geometry of the spaces \(L_p\) and \(\ell_p\) for \(0<p<\infty\), Terminal embeddings, The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme, Prioritized Metric Structures and Embedding

Cites Work

• Ramsey partitions and proximity data structures
• Filling Riemannian manifolds
• Embedding \(l_ p^ m\) into \(l_ 1^ n\)
• On Hilbertian subsets of finite metric spaces
• The metrical interpretation of superreflexivity in Banach spaces
• On Lipschitz embedding of finite metric spaces in Hilbert space
• The dimension of almost spherical sections of convex bodies
• On embedding expanders into \(\ell_p\) spaces
• Lower bounds on the distortion of embedding finite metric spaces in graphs
• Some low distortion metric Ramsey problems
• Extending Lipschitz functions via random metric partitions
• The geometry of graphs and some of its algorithmic applications
• On the distortion required for embedding finite metric spaces into normed spaces
• On the nonexistence of bilipschitz parameterizations and geometric problems about \(A_ \infty\)-weights
• On embedding trees into uniformly convex Banach spaces
• New length bounds for cycle bases
• Ramsey-type theorems for metric spaces with applications to online problems
• On metric Ramsey-type phenomena
• On the nonexistence of uniform homeomorphisms between \(L^ p\)-spaces
• Metric structures in \(L_1\): dimension, snowflakes, and average distortion
• Measured descent: A new embedding method for finite metrics
• Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis
• Subgraph sparsification and nearly optimal ultrasparsifiers
• Divide-and-conquer approximation algorithms via spreading metrics
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• The small-world phenomenon
• Extensions of Lipschitz mappings into a Hilbert space
• Triangulation and embedding using small sets of beacons
• Approximation algorithms for classification problems with pairwise relationships
• Approximate distance oracles
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• On average distortion of embedding metrics into the line and into L ₁
• Euclidean distortion and the sparsest cut
• Improved approximation algorithms for minimum-weight vertex separators
• Volume in General Metric Spaces
• Metric Embeddings with Relaxed Guarantees
• Solving Elliptic Finite Element Systems in Near-Linear Time with Support Preconditioners
• Plongements lipschitziens dans ${\bbfR}\sp n$
• Algorithms for Generating Fundamental Cycles in a Graph
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• Improved search heuristics for the sa-tree
• ON METRIC RAMSEY-TYPE DICHOTOMIES
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• Approximating min-sum k -clustering in metric spaces
• Excluded minors, network decomposition, and multicommodity flow
• Approximate max-flow min-(multi)cut theorems and their applications
• Compact routing with slack in low doubling dimension
• Compact routing with slack
• Approaching Optimality for Solving SDD Linear Systems
• Spanners with Slack
• Algorithms – ESA 2004
• Advances in metric embedding theory
• Local embeddings of metric spaces
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Expander flows, geometric embeddings and graph partitioning
• A tight bound on approximating arbitrary metrics by tree metrics
• Local embeddings of metric spaces
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item