Metric Embedding via Shortest Path Decompositions
From MaRDI portal
Publication:5071090
DOI10.1137/19M1296021OpenAlexW2748812071MaRDI QIDQ5071090
Ofer Neiman, Arnold Filtser, Ittai Abraham, Anupam Gupta
Publication date: 20 April 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/19m1296021
Geometric embeddings of metric spaces (30L05) Computer science (68-XX) Probability theory and stochastic processes (60-XX)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Bandwidth and low dimensional embedding
- On the optimality of gluing over scales
- Cuts, trees and \(\ell_1\)-embeddings of graphs
- Coarse differentiation and multi-flows in planar graphs
- On average distortion of embedding metrics into the line
- Finding small simple cycle separators for 2-connected planar graphs
- On a pursuit game played on graphs for which a minor is excluded
- On Lipschitz embedding of finite metric spaces in Hilbert space
- Multicommodity flows in planar graphs
- Metric decompositions of path-separable graphs
- Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\)
- Tree-width, path-width, and cutwidth
- A lower bound on the distortion of embedding planar metrics into Euclidean space
- The geometry of graphs and some of its algorithmic applications
- Markov convexity and local rigidity of distorted metrics
- On embedding trees into uniformly convex Banach spaces
- Pathwidth, trees, and random embeddings
- Measured descent: A new embedding method for finite metrics
- A Polylogarithmic-Competitive Algorithm for the k -Server Problem
- Extensions of Lipschitz mappings into a Hilbert space
- DIAMOND GRAPHS AND SUPER-REFLEXIVITY
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- Universal approximations for TSP, Steiner tree, and set cover
- Plongements lipschitziens dans ${\bbfR}\sp n$
- Traveling with a Pez Dispenser (or, Routing Issues in MPLS)
- A face cover perspective to ℓ1 embeddings of planar graphs
- Object location using path separators
- Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs
- Approximate Nearest Neighbor Search in Metrics of Planar Graphs
- Near-optimal distortion bounds for embedding doubling spaces into L 1
- Compact oracles for reachability and approximate distances in planar digraphs
- Embedding k-Outerplanar Graphs into l1
- Advances in metric embedding theory
- Efficient distributed approximation algorithms via probabilistic tree embeddings
