Lossless prioritized embeddings

DOI10.1137/21M1436221MaRDI QIDQ5088604zbMATH OpenOpenAlexFDO

Authors Michael Elkin, Ofer Neiman

Publication date 13 July 2022

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/21m1436221

zbMATH Keywords

embeddingmetric spacesprioritized distortion

Mathematics Subject Classification ID

Geometric embeddings of metric spaces (30L05)

Recommendations

• Advances in metric embedding theory
• On notions of distortion and an almost minimum spanning tree with constant average distortion
• Low-distortion embeddings of general metrics into the line

Cites work

• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• A tight bound on approximating arbitrary metrics by tree metrics
• Advances in metric embedding theory
• Approximate distance oracles
• Efficient algorithms for constructing very sparse spanners and emulators
• Extensions of Lipschitz mappings into a Hilbert space
• Graph spanners
• scientific article; zbMATH DE number 5764811 (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 1420896 (Why is no real title available?)
• Labelings vs. Embeddings: On Distributed Representations of Distances
• LATIN 2004: Theoretical Informatics
• Lossless Prioritized Embeddings
• Lower bounds on the distortion of embedding finite metric spaces in graphs
• Lower-Stretch Spanning Trees
• Metric embedding via shortest path decompositions
• Near isometric terminal embeddings for doubling metrics
• Nonlinear dimension reduction via outer bi-Lipschitz extensions
• On Lipschitz embedding of finite metric spaces in Hilbert space
• On notions of distortion and an almost minimum spanning tree with constant average distortion
• On the distortion required for embedding finite metric spaces into normed spaces
• Optimal terminal dimensionality reduction in Euclidean space
• Plongements lipschitziens dans ${\bbfR}\sp n$
• Sparse Sourcewise and Pairwise Distance Preservers
• Terminal embeddings
• The 4/3 additive spanner exponent is tight
• The geometry of graphs and some of its algorithmic applications
• Triangulation and embedding using small sets of beacons
• Using petal-decompositions to build a low stretch spanning tree

Cited in

(5)

• Nonlinear dimension reduction via outer bi-Lipschitz extensions
• Labelings vs. embeddings: on distributed and prioritized representations of distances
• A face cover perspective to _1 embeddings of planar graphs
• Scattering and sparse partitions, and their applications
• On sparse covers of minor free graphs, low dimensional metric embeddings, and other applications

This page was built for publication: Lossless prioritized embeddings

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