A Linear-Time n0.4-Approximation for Longest Common Subsequence
A Linear-Time n0.4-Approximation for Longest Common Subsequence
复制标题
最长公共子序列的线性时间n0.4近似
DOI：
10.1145/3568398
复制
发表时间：
2021
影响因子：
1.3
通讯作者：
Debarati Das
中科院分区：
文献类型：
--
作者：
K. Bringmann;Vincent Cohen;Debarati Das
我们考虑计算两个长度为n的字符串的最长公共子序列（LCS）的经典问题。已有40年历史的二次时间动态规划算法最近被Abboud、Backurs和Vassilevska威廉姆斯[FOCS'15]以及Bringmann和Künnemann [FOCS'15]证明是接近最优的，假设强指数时间假设。这使得社区寻找次二次近似算法的问题。然而，不像编辑距离问题，其中一个常数因子近似在几乎线性的时间是已知的，非常小的进展已经取得了LCS，使其成为一个众所周知的困难的问题，也在近似领域。对于一般的设置，只有一个简单的O（n）/2-近似算法，运行时间为O（n 2-n），对于任何常数0 <n ≤ 1。最近，Hajiaghayi，Seddighin，Seddighin和Sun [SODA'19]的一个突破性结果提供了一个线性时间算法，该算法在期望中产生O（n0.497956-近似;第一次改进了朴素的\（O（\sqrt {n}）\）-近似。在本文中，我们提供了一个算法，在时间O（n2-n）计算一个O（n2 n）/5-近似的高概率，任何0 <n ≤ 1。我们的结果（1）给出了线性时间上的O（n0.4）-近似，改进了Hajiaghayi，Seddighin，Seddighin和Sun的界，（2）提供了一个算法，其近似与任何次二次运行时间O（n2-n2）成比例，改进了对任何n2的O（n2/2）的朴素界，（3）而不是仅仅在期望中，以高概率成功。
We consider the classic problem of computing the Longest Common Subsequence (LCS) of two strings of length n. The 40-year-old quadratic-time dynamic programming algorithm has recently been shown to be near-optimal by Abboud, Backurs, and Vassilevska Williams [FOCS’15] and Bringmann and Künnemann [FOCS’15] assuming the Strong Exponential Time Hypothesis. This has led the community to look for subquadratic approximation algorithms for the problem. Yet, unlike the edit distance problem for which a constant-factor approximation in almost-linear time is known, very little progress has been made on LCS, making it a notoriously difficult problem also in the realm of approximation. For the general setting, only a naive O(nɛ/2-approximation algorithm with running time OŠ(n2-ɛ has been known, for any constant 0 < ɛ ≤ 1. Recently, a breakthrough result by Hajiaghayi, Seddighin, Seddighin, and Sun [SODA’19] provided a linear-time algorithm that yields a O(n0.497956-approximation in expectation; improving upon the naive \(O(\sqrt {n})\) -approximation for the first time. In this paper, we provide an algorithm that in time O(n2-ɛ) computes an OŠ(n2ɛ/5-approximation with high probability, for any 0 < ɛ ≤ 1. Our result (1) gives an OŠ(n0.4-approximation in linear time, improving upon the bound of Hajiaghayi, Seddighin, Seddighin, and Sun, (2) provides an algorithm whose approximation scales with any subquadratic running time O(n2-ɛ), improving upon the naive bound of O(nɛ/2) for any ɛ, and (3) instead of only in expectation, succeeds with high probability.
近线性时间编辑距离：它是一个常数因子
DOI：
10.1109/focs46700.2020.00096
发表时间：
2020
期刊：
IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
Andoni, Alexandr;Nosatzki, Negev Shekel
通讯作者：
Nosatzki, Negev Shekel