DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2023.70

Fitting Tree Metrics with Minimum Disagreements

Authors: Evangelos Kipouridis

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

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.

Cite as

Evangelos Kipouridis. Fitting Tree Metrics with Minimum Disagreements. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 70:1-70:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ESA.2023.70},
  URN =		{urn:nbn:de:0030-drops-187233},
  doi =		{10.4230/LIPIcs.ESA.2023.70},
  annote =	{Keywords: Hierarchical Clustering, Tree Metrics, Minimum Disagreements}
}

Document

DOI: 10.4230/LIPIcs.CPM.2020.19

Longest Common Subsequence on Weighted Sequences

Authors: Evangelos Kipouridis and Kostas Tsichlas

Published in: LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)

Abstract

We consider the general problem of the Longest Common Subsequence (LCS) on weighted sequences. Weighted sequences are an extension of classical strings, where in each position every letter of the alphabet may occur with some probability. Previous results presented a PTAS and noticed that no FPTAS is possible unless P=NP. In this paper we essentially close the gap between upper and lower bounds by improving both. First of all, we provide an EPTAS for bounded alphabets (which is the most natural case), and prove that there does not exist any EPTAS for unbounded alphabets unless FPT=W[1]. Furthermore, under the Exponential Time Hypothesis, we provide a lower bound which shows that no significantly better PTAS can exist for unbounded alphabets. As a side note, we prove that it is sufficient to work with only one threshold in the general variant of the problem.

Cite as

Evangelos Kipouridis and Kostas Tsichlas. Longest Common Subsequence on Weighted Sequences. In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 161, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kipouridis_et_al:LIPIcs.CPM.2020.19,
  author =	{Kipouridis, Evangelos and Tsichlas, Kostas},
  title =	{{Longest Common Subsequence on Weighted Sequences}},
  booktitle =	{31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-149-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{161},
  editor =	{G{\o}rtz, Inge Li and Weimann, Oren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.19},
  URN =		{urn:nbn:de:0030-drops-121443},
  doi =		{10.4230/LIPIcs.CPM.2020.19},
  annote =	{Keywords: WLCS, LCS, weighted sequences, approximation algorithms, lower bound}
}

Search Results

Documents authored by Kipouridis, Evangelos

Fitting Tree Metrics with Minimum Disagreements

Abstract

Cite as

Longest Common Subsequence on Weighted Sequences

Abstract

Cite as

Thanks for your feedback!

Could not send message