Prioritized Metric Structures and Embedding
From MaRDI portal
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 (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
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
