Advances in metric embedding theory

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

Ofer Neiman, Ittai Abraham, Yair Bartal

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

Unnamed Item, Metric Embedding via Shortest Path Decompositions, Lossless Prioritized Embeddings, Bounds on Dimension Reduction in the Nuclear Norm, The least doubling constant of a metric measure space, Covering Metric Spaces by Few Trees, Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs, Unnamed Item, Labelings vs. embeddings: on distributed and prioritized representations of distances, Volume in general metric spaces, Dimensionality reduction of complex metastable systems via kernel embeddings of transition manifolds, Unavoidable minors for graphs with large \(\ell_p\)-dimension, Efficient approximation of the metric CVRP in spaces of fixed doubling dimension, An average John theorem, Approximation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension, Light spanners for high dimensional norms via stochastic decompositions, Covering metric spaces by few trees, Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension, Embeddability of snowflaked metrics with applications to the nonlinear geometry of the spaces \(L_p\) and \(\ell_p\) for \(0<p<\infty\), On notions of distortion and an almost minimum spanning tree with constant average distortion, Terminal embeddings, The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme, Prioritized Metric Structures and Embedding

Cites Work

• 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
• 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