Metric Embedding via Shortest Path Decompositions

DOI10.1137/19M1296021MaRDI QIDQ5071090zbMATH OpenOpenAlexFDO

Authors Ittai Abraham, Arnold Filtser, Anupam Gupta, Ofer Neiman

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

zbMATH Keywords

\(\ell_p\) spacesmetric embeddingspathwidthsparsest cut

Mathematics Subject Classification ID

Geometric embeddings of metric spaces (30L05) Probability theory and stochastic processes (60-XX) Computer science (68-XX)

Recommendations

• Metric embedding via shortest path decompositions
• On average distortion of embedding metrics into the line and into l₁
• Plane embeddings of planar graph metrics
• Plane embeddings of planar graph metrics
• A lower bound on the distortion of embedding planar metrics into Euclidean space

Cites work

• A face cover perspective to ℓ₁ embeddings of planar graphs
• A lower bound on the distortion of embedding planar metrics into Euclidean space
• A polylogarithmic-competitive algorithm for the k-server problem
• Advances in metric embedding theory
• Approximate nearest neighbor search in metrics of planar graphs
• Bandwidth and low dimensional embedding
• Coarse differentiation and multi-flows in planar graphs
• Compact oracles for reachability and approximate distances in planar digraphs
• Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• DIAMOND GRAPHS AND SUPER-REFLEXIVITY
• Efficient distributed approximation algorithms via probabilistic tree embeddings
• Embedding k-Outerplanar Graphs into l1
• Embedding the diamond graph in L_p and dimension reduction in L₁
• Extensions of Lipschitz mappings into a Hilbert space
• Finding small simple cycle separators for 2-connected planar graphs
• scientific article; zbMATH DE number 219228 (Why is no real title available?)
• scientific article; zbMATH DE number 6297701 (Why is no real title available?)
• Markov convexity and local rigidity of distorted metrics
• Measured descent: A new embedding method for finite metrics
• Metric decompositions of path-separable graphs
• Multicommodity flows in planar graphs
• Near-optimal distortion bounds for embedding doubling spaces into L ₁
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Object location using path separators
• On a pursuit game played on graphs for which a minor is excluded
• On average distortion of embedding metrics into the line
• On embedding trees into uniformly convex Banach spaces
• On Lipschitz embedding of finite metric spaces in Hilbert space
• On the optimality of gluing over scales
• Pathwidth, trees, and random embeddings
• Plongements lipschitziens dans ${\bbfR}\sp n$
• The geometry of graphs and some of its algorithmic applications
• Traveling with a Pez Dispenser (or, Routing Issues in MPLS)
• Tree-width, path-width, and cutwidth
• Universal approximations for TSP, Steiner tree, and set cover

Cited in

(5)

• Optimal Embedding into Star Metrics
• Corrigendum: Metric Embedding via Shortest Path Decompositions
• Optimal padded decomposition for bounded treewidth graphs
• A face cover perspective to _1 embeddings of planar graphs
• On sparse covers of minor free graphs, low dimensional metric embeddings, and other applications

This page was built for publication: Metric Embedding via Shortest Path Decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5071090)