Advances in metric embedding theory
Advances in metric embedding theory (scientific article; zbMATH DE number 5985533)
The paper contains numerous improvements of the existing results on embeddings of metric spaces into Banach spaces. Many of these improvements are motivated by applications. One of the directions in which the existing results are improved is the following: many of the known results estimate the worst-case distortion, that is, if we restrict to non-contractive embeddings, one estimates the maximal expansion of distances. However, for many applications average expansion is more interesting. The authors construct an embedding (Theorem 2) which simultaneously achieves the best possible order of the worst-case Euclidean distortion and has uniformly bounded average distortion. The authors introduce several different notions of average distortion and prove some analogues of the above stated result for them. The authors improve the known bound for the dimension of low-distortion embeddings into \(\ell_p\) by proving (Theorem 4): For any \(1\leq p\leq\infty\), every \(n\)-point metric space embeds in \(\ell_p\) with distortion \(O(\log n)\) in dimension \(O(\log n)\). The authors prove the following result which connects the intrinsic dimension of a doubling space and its embedding dimension (Theorem 8): There exists a universal constant \(C\) such that for any \(n\)-point metric space \((X, d)\) and any \(C/\log\log n <\theta\leq 1\), there exists an embedding \(f :X\to\ell_p^D\) with distortion \(O(\log^{1+\theta}n)\) where \(D = O(\text{dim}(X)/\theta)\). The authors prove also interesting results on partial embeddings (the case where we care only about some of the distances) and on scaling distortion (the case where we allow relatively large distortions for relatively small amounts of distances). The main tool for the embedding theorems proved in this paper is the notion of uniformly padded probabilistic partitions of a metric space. This 100-page paper contains many other versions of the results mentioned above and some related results, the purpose of this review was only to mention some of the directions which were studied in the paper.
- A nonlinear approach to dimension reduction
- A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
- A tight bound on approximating arbitrary metrics by tree metrics
- Advances in metric embedding theory
- Algorithms for Generating Fundamental Cycles in a Graph
- Algorithms – ESA 2004
- An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
- Approaching optimality for solving SDD linear systems
- Approximate distance oracles
- Approximate max-flow min-(multi)cut theorems and their applications
- Approximating min-sum k -clustering in metric spaces
- Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
- Approximation algorithms for the 0-extension problem
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- Compact routing with slack
- Compact routing with slack in low doubling dimension
- Dimensionality reduction: beyond the Johnson-Lindenstrauss bound
- Divide-and-conquer approximation algorithms via spreading metrics
- Embedding \(l_ p^ m\) into \(l_ 1^ n\)
- Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
- Euclidean distortion and the sparsest cut (extended abstract)
- Excluded minors, network decomposition, and multicommodity flow
- Expander flows, geometric embeddings and graph partitioning
- Extending Lipschitz functions via random metric partitions
- Extensions of Lipschitz mappings into a Hilbert space
- Filling Riemannian manifolds
- scientific article; zbMATH DE number 432834 (Why is no real title available?)
- scientific article; zbMATH DE number 4169644 (Why is no real title available?)
- scientific article; zbMATH DE number 5764808 (Why is no real title available?)
- scientific article; zbMATH DE number 5764811 (Why is no real title available?)
- scientific article; zbMATH DE number 1303559 (Why is no real title available?)
- scientific article; zbMATH DE number 714526 (Why is no real title available?)
- scientific article; zbMATH DE number 2079348 (Why is no real title available?)
- scientific article; zbMATH DE number 1749054 (Why is no real title available?)
- scientific article; zbMATH DE number 1775400 (Why is no real title available?)
- scientific article; zbMATH DE number 1789916 (Why is no real title available?)
- Improved approximation algorithms for minimum-weight vertex separators
- Improved search heuristics for the sa-tree
- Local embeddings of metric spaces
- Local embeddings of metric spaces
- Lower bounds on the distortion of embedding finite metric spaces in graphs
- Measured descent: A new embedding method for finite metrics
- Metric embeddings with relaxed guarantees
- Metric structures in \(L_1\): dimension, snowflakes, and average distortion
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- New length bounds for cycle bases
- On average distortion of embedding metrics into the line and into l₁
- On embedding expanders into \(\ell_p\) spaces
- On embedding trees into uniformly convex Banach spaces
- On Hilbertian subsets of finite metric spaces
- On Lipschitz embedding of finite metric spaces in Hilbert space
- ON METRIC RAMSEY-TYPE DICHOTOMIES
- 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 the nonexistence of uniform homeomorphisms between \(L^ p\)-spaces
- Plongements lipschitziens dans ${\bbfR}\sp n$
- Ramsey partitions and proximity data structures
- Ramsey-type theorems for metric spaces with applications to online problems
- Solving elliptic finite element systems in near-linear time with support preconditioners
- Some low distortion metric Ramsey problems
- Spanners with Slack
- Subgraph sparsification and nearly optimal ultrasparsifiers
- The dimension of almost spherical sections of convex bodies
- The geometry of graphs and some of its algorithmic applications
- The metrical interpretation of superreflexivity in Banach spaces
- The small-world phenomenon: an algorithmic perspective
- Triangulation and embedding using small sets of beacons
- Volume in general metric spaces
- On embedding expanders into \(\ell_p\) 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
- On \(L_1\)-embeddability of unions of \(L_1\)-embeddable metric spaces and of twisted unions of hypercubes
- 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
- Nonembeddability theorems via Fourier analysis
- Measured descent: A new embedding method for finite metrics
- Low dimensional embeddings of doubling metrics
- The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
- Metric Spaces Admitting Low-distortion Embeddings into All n-dimensional Banach Spaces
- Low distortion metric embedding into constant dimension
- Local global tradeoffs in metric embeddings
- The metric geometry of the Hamming cube and applications
- Low dimensional embeddings of doubling metrics
- Ultra-low-dimensional embeddings for doubling metrics
- Metric embeddings with outliers
- Probabilistic clustering of high dimensional norms
- Constant-distortion embeddings of Hausdorff metrics into constant-dimensional \(\ell_p\) spaces
- Volume in general metric spaces
- scientific article; zbMATH DE number 843592 (Why is no real title available?)
- FPT algorithms for embedding into low complexity graphic metrics
- Metric Embedding via Shortest Path Decompositions
- Lossless prioritized embeddings
- Covering Metric Spaces by Few Trees
- Bounds on Dimension Reduction in the Nuclear Norm
- The least doubling constant of a metric measure space
- Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
- Algorithms – ESA 2004
- scientific article; zbMATH DE number 7650073 (Why is no real title available?)
- Advances in metric embedding theory
- Local embeddings of metric spaces
- Local embeddings of metric spaces
- On dominated _1 metrics
- Labelings vs. embeddings: on distributed and prioritized representations of distances
- Scattering and sparse partitions, and their applications
- Bourgain's discretization theorem
- Metric embeddings -- beyond one-dimensional distortion
- A face cover perspective to _1 embeddings of planar graphs
- Scattering and sparse partitions, and their applications
- Optimal Euclidean tree covers
- Constant distortion embeddings of symmetric diversities
- On sparse covers of minor free graphs, low dimensional metric embeddings, and other applications
This page was built for publication: Advances in metric embedding theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5894374)
