TY - GEN

T1 - Longest Common Subsequence on Weighted Sequences.

AU - Kipouridis, Evangelos

AU - Tsichlas, K.

N1 - Received the Alberto Apostolico Best Paper Award.

PY - 2020/6

Y1 - 2020/6

N2 - 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.

AB - 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.

UR - https://cpm2020.compute.dtu.dk/CPM_best_paper_award.pdf

UR - https://www.youtube.com/watch?v=Skrci0vF7ds

UR - http://2020.highlightsofalgorithms.org/shorttalks

UR - http://pages.cs.aueb.gr/othersites/ACAC20/index.php

UR - https://youtu.be/iFapquV7TYU?t=8126

U2 - 10.4230/LIPIcs.CPM.2020.19

DO - 10.4230/LIPIcs.CPM.2020.19

M3 - Article in proceedings

SN - 978-3-95977-149-8

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - Longest Common Subsequence on Weighted Sequences.

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

ER -