2026-07-23T22:33:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18827 2024-03-06T11:02:40Z ddc:004 open_access

Probabilistic Metric Embedding via Metric Labeling Munagala, Kamesh Sankar, Govind S. Taylor, Erin Metric Embedding Approximation Algorithms Ultrametrics 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kamesh Munagala and Govind S. Sankar and Erin Taylor 2023 Is Part Of LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2023.2 urn:nbn:de:0030-drops-188279 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.2 eng https://creativecommons.org/licenses/by/4.0/legalcode