Quasimetric Embeddings and Their Applications

Authors Facundo Mémoli, Anastasios Sidiropoulos, Vijay Sridhar



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.85.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Facundo Mémoli
Anastasios Sidiropoulos
Vijay Sridhar

Cite AsGet BibTex

Facundo Mémoli, Anastasios Sidiropoulos, and Vijay Sridhar. Quasimetric Embeddings and Their Applications. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 85:1-85:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICALP.2016.85

Abstract

We study generalizations of classical metric embedding results to the case of quasimetric spaces; that is, spaces that do not necessarily satisfy symmetry. Quasimetric spaces arise naturally from the shortest-path distances on directed graphs. Perhaps surprisingly, very little is known about low-distortion embeddings for quasimetric spaces. Random embeddings into ultrametric spaces are arguably one of the most successful geometric tools in the context of algorithm design. We extend this to the quasimetric case as follows. We show that any n-point quasimetric space supported on a graph of treewidth t admits a random embedding into quasiultrametric spaces with distortion O(t*log^2(n)), where quasiultrametrics are a natural generalization of ultrametrics. This result allows us to obtain t*log^{O(1)}(n)-approximation algorithms for the Directed Non-Bipartite Sparsest-Cut and the Directed Multicut problems on n-vertex graphs of treewidth t, with running time polynomial in both n and t. The above results are obtained by considering a generalization of random partitions to the quasimetric case, which we refer to as random quasipartitions. Using this definition and a construction of [Chuzhoy and Khanna 2009] we derive a polynomial lower bound on the distortion of random embeddings of general quasimetric spaces into quasiultrametric spaces. Finally, we establish a lower bound for embedding the shortest-path quasimetric of a graph G into graphs that exclude G as a minor. This lower bound is used to show that several embedding results from the metric case do not have natural analogues in the quasimetric setting.
Keywords
  • metric embeddings
  • quasimetrics
  • outliers
  • random embeddings
  • treewidth
  • Directed Sparsest-Cut
  • Directed Multicut

Metrics

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

References

  1. Ittai Abraham, Yair Bartal, and Ofer Neiman. Nearly tight low stretch spanning trees. arXiv preprint arXiv:0808.2017, 2008. Google Scholar
  2. Amit Agarwal, Noga Alon, and Moses S Charikar. Improved approximation for directed cut problems. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 671-680. ACM, 2007. Google Scholar
  3. Sanjeev Arora, James Lee, and Assaf Naor. Euclidean distortion and the sparsest cut. Journal of the American Mathematical Society, 21(1):1-21, 2008. Google Scholar
  4. Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on, pages 184-193. IEEE, 1996. Google Scholar
  5. Yair Bartal. On approximating arbitrary metrices by tree metrics. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 161-168. ACM, 1998. Google Scholar
  6. Glencora Borradaile, James R Lee, and Anastasios Sidiropoulos. Randomly removing g handles at once. In Proceedings of the twenty-fifth annual symposium on Computational geometry, pages 371-376. ACM, 2009. Google Scholar
  7. Gruia Calinescu, Howard Karloff, and Yuval Rabani. Approximation algorithms for the 0-extension problem. SIAM Journal on Computing, 34(2):358-372, 2005. Google Scholar
  8. Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Directed metrics and directed graph partitioning problems. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 51-60. Society for Industrial and Applied Mathematics, 2006. Google Scholar
  9. Julia Chuzhoy and Sanjeev Khanna. Polynomial flow-cut gaps and hardness of directed cut problems. Journal of the ACM (JACM), 56(2):6, 2009. Google Scholar
  10. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 448-455. ACM, 2003. Google Scholar
  11. Uriel Feige, MohammadTaghi Hajiaghayi, and James R Lee. Improved approximation algorithms for minimum weight vertex separators. SIAM Journal on Computing, 38(2):629-657, 2008. Google Scholar
  12. Mohammad Taghi Hajiaghayi and Harald Räcke. An-approximation algorithm for directed sparsest cut. Information Processing Letters, 97(4):156-160, 2006. Google Scholar
  13. Piotr Indyk and Jiri Matoušek. Low-distortion embeddings of finite metric spaces. Handbook of Discrete and Computational Geometry, page 177, 2004. Google Scholar
  14. Piotr Indyk and Anastasios Sidiropoulos. Probabilistic embeddings of bounded genus graphs into planar graphs. In Proceedings of the twenty-third annual symposium on Computational geometry, pages 204-209. ACM, 2007. Google Scholar
  15. Jonathan A Kelner, James R Lee, Gregory N Price, and Shang-Hua Teng. Metric uniformization and spectral bounds for graphs. Geometric and Functional Analysis, 21(5):1117-1143, 2011. Google Scholar
  16. Philip Klein, Serge A Plotkin, and Satish Rao. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 682-690. ACM, 1993. Google Scholar
  17. Yana Kortsarts, Guy Kortsarz, and Zeev Nutov. Greedy approximation algorithms for directed multicuts. Networks, 45(4):214-217, 2005. Google Scholar
  18. Robert Krauthgamer, James R Lee, Manor Mendel, and Assaf Naor. Measured descent: A new embedding method for finite metrics. Geometric &Functional Analysis GAFA, 15(4):839-858, 2005. Google Scholar
  19. James R Lee and Assaf Naor. Extending lipschitz functions via random metric partitions. Inventiones mathematicae, 160(1):59-95, 2005. Google Scholar
  20. James R Lee and Anastasios Sidiropoulos. On the geometry of graphs with a forbidden minor. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 245-254. ACM, 2009. Google Scholar
  21. James R Lee and Anastasios Sidiropoulos. Genus and the geometry of the cut graph. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 193-201. Society for Industrial and Applied Mathematics, 2010. Google Scholar
  22. Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215-245, 1995. Google Scholar
  23. Anastasios Sidiropoulos. Optimal stochastic planarization. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 163-170. IEEE, 2010. 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