Prioritized Metric Structures and Embedding

DOI10.1145/2746539.2746623zbMath1321.68222arXiv1502.05543OpenAlexW2094568665MaRDI QIDQ2941541

Ofer Neiman, Arnold Filtser, Michael Elkin

Publication date: 21 August 2015

Published in: SIAM Journal on Computing, Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1502.05543

zbMATH Keywords

routingdistance oraclesmetric embeddingpriorities

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05) Signed and weighted graphs (05C22)

Related Items (8)

Terminal embeddings ⋮ Lossless Prioritized Embeddings ⋮ Near isometric terminal embeddings for doubling metrics ⋮ Prioritized Metric Structures and Embedding ⋮ Labelings vs. embeddings: on distributed and prioritized representations of distances ⋮ Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm ⋮ On notions of distortion and an almost minimum spanning tree with constant average distortion ⋮ Near Isometric Terminal Embeddings for Doubling Metrics

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ramsey partitions and proximity data structures
• Lower bounds for local versions of dimension reductions
• The metrical interpretation of superreflexivity in Banach spaces
• On Lipschitz embedding of finite metric spaces in Hilbert space
• On sparse spanners of weighted graphs
• The dimension of almost spherical sections of convex bodies
• Lower bounds on the distortion of embedding finite metric spaces in graphs
• The geometry of graphs and some of its algorithmic applications
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Approximate Distance Oracles with Improved Bounds
• Prioritized Metric Structures and Embedding
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Extensions of Lipschitz mappings into a Hilbert space
• Triangulation and embedding using small sets of beacons
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• A Separator Theorem for Planar Graphs
• Routing with Polynomial Communication-Space Trade-Off
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion
• Distance Labels with Optimal Local Stretch
• Shortest-path queries in static networks
• Object location using path separators
• Approximate distance oracles with constant query time
• Spanners with Slack
• A Polylogarithmic-Competitive Algorithm for the k-Server Problem
• Automata, Languages and Programming
• Approximate Distance Oracles with Improved Query Time
• Advances in metric embedding theory
• A tight bound on approximating arbitrary metrics by tree metrics
• Efficient distributed approximation algorithms via probabilistic tree embeddings

This page was built for publication: Prioritized Metric Structures and Embedding