License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.2
URN: urn:nbn:de:0030-drops-188279
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18827/
Go to the corresponding LIPIcs Volume Portal

Munagala, Kamesh ; Sankar, Govind S. ; Taylor, Erin

Probabilistic Metric Embedding via Metric Labeling

pdf-format:
LIPIcs-APPROX2.pdf (0.6 MB)

Abstract

We consider probabilistic embedding of metric spaces into ultra-metrics (or equivalently to a constant factor, into hierarchically separated trees) to minimize the expected distortion of any pairwise distance. Such embeddings have been widely used in network design and online algorithms. Our main result is a polynomial time algorithm that approximates the optimal distortion on any instance to within a constant factor. We achieve this via a novel LP formulation that reduces this problem to a probabilistic version of uniform metric labeling.

BibTeX - Entry

@InProceedings{munagala_et_al:LIPIcs.APPROX/RANDOM.2023.2,
  author =	{Munagala, Kamesh and Sankar, Govind S. and Taylor, Erin},
  title =	{{Probabilistic Metric Embedding via Metric Labeling}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{2:1--2:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18827},
  URN =		{urn:nbn:de:0030-drops-188279},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.2},
  annote =	{Keywords: Metric Embedding, Approximation Algorithms, Ultrametrics}
}

Keywords: Metric Embedding, Approximation Algorithms, Ultrametrics
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Issue Date: 2023
Date of publication: 04.09.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI