Approximating approximate distance oracles

DOI10.4230/LIPICS.ITCS.2017.52MaRDI QIDQ4638107zbMATH OpenFDO

Authors Michael Dinitz, Ze Yu Zhang

Publication date 3 May 2018

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

zbMATH Keywords

approximation algorithmsdistance oracles

Mathematics Subject Classification ID

Data structures (68P05) Approximation algorithms (68W25)

Recommendations

• Distance oracles beyond the Thorup-Zwick bound
• Approximate distance oracles with improved query time
• Approximate distance oracles with improved bounds
• Approximate distance oracles with improved stretch for sparse graphs
• Approximate distance oracles with constant query time

Cites work

• A Parallel Repetition Theorem
• A threshold of ln n for approximating set cover
• Analytical approach to parallel repetition
• Approximate distance oracles
• Approximate distance oracles with constant query time
• Approximate distance oracles with improved bounds
• Approximate distance oracles with improved query time
• Approximating approximate distance oracles
• Approximating low-stretch spanners
• Approximation algorithms for spanner problems and directed Steiner forest
• Directed spanners via flow-based linear programs
• Heuristics for the fixed cost median problem
• scientific article; zbMATH DE number 6696497 (Why is no real title available?)
• scientific article; zbMATH DE number 1330032 (Why is no real title available?)
• Metric embeddings with relaxed guarantees
• On approximate distance labels and routing schemes with affine stretch
• Spanners with Slack

Cited in

(4)

• Compact Oracles for Approximate Distances Around Obstacles in the Plane
• Approximating approximate distance oracles
• Analysis and Experimental Evaluation of Time-Dependent Distance Oracles
• Distance Oracles for Stretch Less Than 2

This page was built for publication: Approximating approximate distance oracles

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