Advances in metric embedding theory

DOI10.1016/j.aim.2011.08.003zbMath1250.46016OpenAlexW2017427469MaRDI 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 reductionmetric spacebilipschitz embedding

Mathematics Subject Classification ID

Metric spaces, metrizability (54E35) Distance in graphs (05C12) Approximation algorithms (68W25) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85)

Related Items (23)

Metric Embedding via Shortest Path Decompositions ⋮ Covering metric spaces by few trees ⋮ Terminal embeddings ⋮ Lossless Prioritized Embeddings ⋮ Prioritized Metric Structures and Embedding ⋮ Labelings vs. embeddings: on distributed and prioritized representations of distances ⋮ Unnamed Item ⋮ Bounds on Dimension Reduction in the Nuclear Norm ⋮ Unnamed Item ⋮ Volume in general metric spaces ⋮ 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\) ⋮ 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 ⋮ The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme ⋮ 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 ⋮ On notions of distortion and an almost minimum spanning tree with constant average distortion ⋮ Light spanners for high dimensional norms via stochastic decompositions

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

This page was built for publication: Advances in metric embedding theory