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.ESA.2023.70
URN: urn:nbn:de:0030-drops-187233
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18723/
Go to the corresponding LIPIcs Volume Portal

Kipouridis, Evangelos

Fitting Tree Metrics with Minimum Disagreements

pdf-format:
LIPIcs-ESA-2023-70.pdf (0.6 MB)

Abstract

In the L₀ Fitting Tree Metrics problem, we are given all pairwise distances among the elements of a set V and our output is a tree metric on V. The goal is to minimize the number of pairwise distance disagreements between the input and the output. We provide an O(1) approximation for L₀ Fitting Tree Metrics, which is asymptotically optimal as the problem is APX-Hard.
For p ≥ 1, solutions to the related L_p Fitting Tree Metrics have typically used a reduction to L_p Fitting Constrained Ultrametrics. Even though in FOCS '22 Cohen-Addad et al. solved L₀ Fitting (unconstrained) Ultrametrics within a constant approximation factor, their results did not extend to tree metrics.
We identify two possible reasons, and provide simple techniques to circumvent them. Our framework does not modify the algorithm from Cohen-Addad et al. It rather extends any ρ approximation for L₀ Fitting Ultrametrics to a 6ρ approximation for L₀ Fitting Tree Metrics in a blackbox fashion.

BibTeX - Entry

@InProceedings{kipouridis:LIPIcs.ESA.2023.70,
  author =	{Kipouridis, Evangelos},
  title =	{{Fitting Tree Metrics with Minimum Disagreements}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{70:1--70:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18723},
  URN =		{urn:nbn:de:0030-drops-187233},
  doi =		{10.4230/LIPIcs.ESA.2023.70},
  annote =	{Keywords: Hierarchical Clustering, Tree Metrics, Minimum Disagreements}
}

Keywords: Hierarchical Clustering, Tree Metrics, Minimum Disagreements
Collection: 31st Annual European Symposium on Algorithms (ESA 2023)
Issue Date: 2023
Date of publication: 30.08.2023

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