Prioritized Metric Structures and Embedding
From MaRDI portal
Publication:2941541
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
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05) Signed and weighted graphs (05C22)
Related Items
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
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
