Approximating Binary Longest Common Subsequence in Almost-Linear Time
Approximating Binary Longest Common Subsequence in Almost-Linear Time
复制标题
在几乎线性时间内逼近二进制最长公共子序列
DOI：
10.1145/3564246.3585104
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Li, Ray
中科院分区：
文献类型：
--
作者：
He, Xiaoyu;Li, Ray
最长公共子序列（LCS）是一个基本的字符串相似性度量，计算两个字符串的LCS是一个经典的算法问题。教科书上的动态规划算法给出了二次时间的精确算法，这在合理的细粒度复杂性假设下基本上是最好的，所以一个自然的问题是找到更快的近似算法。当输入是两个二进制字符串时，在线性时间中有一个简单的1/2近似：计算最长的公共全0或全1子序列。即使在真正的次二次时间中，是否有可能得到更好的近似值，这一点一直是开放的。Rubinstein和Song证明，在两个输入字符串长度相等的假设下，答案是肯定的。我们解决了这个问题，把他们的结果推广到不等长字符串，证明了对任意ε>0，存在δ>0和一个在n1 +ε时间内运行的二进制LCS的（1/2+δ）-近似算法.作为我们的结果和Akmal和Vassilevska-Williams的结果的一个结果，对于任意ε>0，在n1 +ε时间上存在LCS超q元串的（1/q+δ）-逼近.我们的技术建立在Guruswami，He和Li最近的工作之上，他们证明了容许删除错误的纠错码的新界.他们证明了一个组合的“结构引理”的字符串分类，他们根据自己的振荡模式。我们证明和使用的算法推广这个结构引理，这可能是独立的利益。
The Longest Common Subsequence (LCS) is a fundamental string similarity measure, and computing the LCS of two strings is a classic algorithms question. A textbook dynamic programming algorithm gives an exact algorithm in quadratic time, and this is essentially best possible under plausible fine-grained complexity assumptions, so a natural problem is to find faster approximation algorithms. When the inputs are two binary strings, there is a simple 1/2-approximation in linear time: compute the longest common all-0s or all-1s subsequence. It has been open whether a better approximation is possible even in truly subquadratic time. Rubinstein and Song showed that the answer is yes under the assumption that the two input strings have equal lengths. We settle the question, generalizing their result to unequal length strings, proving that, for any ε>0, there exists δ>0 and a (1/2+δ)-approximation algorithm for binary LCS that runs inn1+εtime. As a consequence of our result and a result of Akmal and Vassilevska-Williams, for any ε>0, there exists a (1/q+δ)-approximation for LCS overq-ary strings inn1+εtime.Our techniques build on the recent work of Guruswami, He, and Li who proved new bounds for error-correcting codes tolerating deletion errors. They prove a combinatorial “structure lemma” for strings which classifies them according to their oscillation patterns. We prove and use an algorithmic generalization of this structure lemma, which may be of independent interest.
登录
查看更多内容
近线性时间编辑距离：它是一个常数因子
DOI：
10.1109/focs46700.2020.00096
发表时间：
2020
期刊：
IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
Andoni, Alexandr;Nosatzki, Negev Shekel
通讯作者：
Nosatzki, Negev Shekel
选定的组合研究问题。
DOI：
--
发表时间：
1972
期刊：
影响因子：
--
作者：
V. Chvátal;D. Klarner;D. Knuth
通讯作者：
D. Knuth
对抗性位删除的零率阈值小于 1/2
DOI：
--
发表时间：
2021
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
V. Guruswami;Xiaoyu He;Ray Li
通讯作者：
Ray Li
最长公共子序列的线性时间n0.4近似
影响因子：
1.3
作者：
K. Bringmann;Vincent Cohen;Debarati Das
通讯作者：
Debarati Das
影响因子：
2.5
作者：
B. Bukh;V. Guruswami;J. Håstad
通讯作者：
J. Håstad