Document Open Access Logo

Approximating Approximate Distance Oracles

Authors Michael Dinitz, Zeyu Zhang

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2017.52.pdf
  • Filesize: 489 kB
  • 14 pages

Document Identifiers

Author Details

Michael Dinitz
Zeyu Zhang

Cite As Get BibTex

Michael Dinitz and Zeyu Zhang. Approximating Approximate Distance Oracles. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ITCS.2017.52

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 per-instance 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 well-defined, we restrict our attention to well-known 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 Thorup-Zwick distance oracle, as well as the problem of finding the smallest P\v{a}tra\c{s}cu-Roditty 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^{k-1}}}) integrality gap for the more general stretch (2k-1) Thorup-Zwick 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.

Subject Classification

Keywords
  • distance oracles
  • approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ittai Abraham and Cyril Gavoille. On approximate distance labels and routing schemes with affine stretch. In Proceedings of the International Symposium on Distributed Computing (DISC), pages 404-415. Springer, 2011. Google Scholar
  2. Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Approximation algorithms for spanner problems and directed steiner forest. Information and Computation, 222:93-107, 2013. Google Scholar
  3. T-H Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon Kleinberg, and Aleksandrs Slivkins. Metric embeddings with relaxed guarantees. SIAM Journal on Computing, 38(6):2303-2329, 2009. Google Scholar
  4. T-H Hubert Chan, Michael Dinitz, and Anupam Gupta. Spanners with slack. In European Symposium on Algorithms, pages 196-207. Springer, 2006. Google Scholar
  5. Shiri Chechik. Approximate distance oracles with constant query time. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 654-663. ACM, 2014. Google Scholar
  6. Shiri Chechik. Approximate distance oracles with improved bounds. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pages 1-10. ACM, 2015. Google Scholar
  7. Eden Chlamtác and Michael Dinitz. Lowest degree k-spanner: Approximation and hardness. In Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), volume 28, pages 80-95. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014. Google Scholar
  8. Eden Chlamtac, Michael Dinitz, and Robert Krauthgamer. Everywhere-sparse spanners via dense subgraphs. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 758-767. IEEE Computer Society, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.61.
  9. Michael Dinitz and Robert Krauthgamer. Directed spanners via flow-based linear programs. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, pages 323-332. ACM, 2011. Google Scholar
  10. Michael Dinitz and Zeyu Zhang. Approximating approximate distance oracles. Full version. URL: https://arxiv.org/abs/1612.05623.
  11. Michael Dinitz and Zeyu Zhang. Approximating low-stretch spanners. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 821-840. SIAM, 2016. Google Scholar
  12. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 624-633. ACM, 2014. Google Scholar
  13. Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634-652, 1998. Google Scholar
  14. Dorit S Hochbaum. Heuristics for the fixed cost median problem. Mathematical programming, 22(1):148-162, 1982. Google Scholar
  15. Guy Joseph Jacobson. Succinct Static Data Structures. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, USA, 1988. Google Scholar
  16. Mihai Patrascu and Liam Roditty. Distance oracles beyond the thorup-zwick bound. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 815-823. IEEE, 2010. Google Scholar
  17. Mihai Patrascu, Liam Roditty, and Mikkel Thorup. A new infinity of distance oracles for sparse graphs. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 738-747. IEEE, 2012. Google Scholar
  18. Ran Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763-803, 1998. Google Scholar
  19. Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journal of the ACM (JACM), 52(1):1-24, 2005. Google Scholar
  20. Vijay V Vazirani. Approximation algorithms. Springer Science &Business Media, 2013. Google Scholar
  21. Christian Wulff-Nilsen. Approximate distance oracles with improved query time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 539-549. Society for Industrial and Applied Mathematics, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact