Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Mémoli, Facundo; Sidiropoulos, Anastasios; Sridhar, Vijay http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-62007
URL:

; ;

Quasimetric Embeddings and Their Applications

pdf-format:


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.

BibTeX - Entry

@InProceedings{mmoli_et_al:LIPIcs:2016:6200,
  author =	{Facundo M{\'e}moli and Anastasios Sidiropoulos and Vijay Sridhar},
  title =	{{Quasimetric Embeddings and Their Applications}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{85:1--85:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6200},
  URN =		{urn:nbn:de:0030-drops-62007},
  doi =		{10.4230/LIPIcs.ICALP.2016.85},
  annote =	{Keywords: metric embeddings, quasimetrics, outliers, random embeddings, treewidth, Directed Sparsest-Cut, Directed Multicut}
}

Keywords: metric embeddings, quasimetrics, outliers, random embeddings, treewidth, Directed Sparsest-Cut, Directed Multicut
Seminar: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue date: 2016
Date of publication: 2016


DROPS-Home | Fulltext Search | Imprint Published by LZI