Dinitz, Michael ;
Zhang, Zeyu
Approximating Approximate Distance Oracles
Abstract
Given a finite metric space (V,d), an approximate distance oracle is a data structure which, when queried on two points u,v \in V, returns an approximation to the the actual distance between u and v which is within some bounded stretch factor of the true distance. There has been significant work on the tradeoff between the important parameters of approximate distance oracles (and in particular between the size, stretch, and query time), but in this paper we take a different point of view, that of perinstance optimization. If we are given an particular input metric space and stretch bound, can we find the smallest possible approximate distance oracle for that particular input? Since this question is not even welldefined, we restrict our attention to wellknown classes of approximate distance oracles, and study whether we can optimize over those classes.
In particular, we give an O(\log n)approximation to the problem of finding the smallest stretch 3 ThorupZwick distance oracle, as well as the problem of finding the smallest P\v{a}tra\c{s}cuRoditty distance oracle. We also prove a matching \Omega(\log n) lower bound for both problems, and an \Omega(n^{\frac{1}{k}\frac{1}{2^{k1}}}) integrality gap for the more general stretch (2k1) ThorupZwick distance oracle. We also consider the problem of approximating the best TZ or PR approximate distance oracle with outliers, and show that more advanced techniques (SDP relaxations in particular) allow us to optimize even in the presence of outliers.
BibTeX  Entry
@InProceedings{dinitz_et_al:LIPIcs:2017:8169,
author = {Michael Dinitz and Zeyu Zhang},
title = {{Approximating Approximate Distance Oracles}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {52:152:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770293},
ISSN = {18688969},
year = {2017},
volume = {67},
editor = {Christos H. Papadimitriou},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8169},
URN = {urn:nbn:de:0030drops81692},
doi = {10.4230/LIPIcs.ITCS.2017.52},
annote = {Keywords: distance oracles, approximation algorithms}
}
28.11.2017
Keywords: 

distance oracles, approximation algorithms 
Seminar: 

8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Issue date: 

2017 
Date of publication: 

28.11.2017 