论文标题
线性时间近似LCS：击败$ \ sqrt {n} $屏障
Approximating LCS in Linear Time: Beating the $\sqrt{n}$ Barrier
论文作者
论文摘要
最长的常见子序列（LCS）是组合优化中最基本的问题之一。除了理论上的重要性外，LCS在生物信息学，修订控制系统和数据比较程序中还具有巨大的应用。尽管一个简单的动态程序在二次时间内计算LCS，但最近已证明，该问题承认有条件的下限，并且在真正的次级时间时期可能无法解决。除此之外，相对于近似算法，LCS也很难。除了在时间$ o（n^{2-2x}）中获得$ n^{x} $近似解决方案的微不足道采样技术外，lcs $ o（n^{2-2x}）$什么都不知道。这与其双重问题编辑距离形成鲜明对比，在过去的二十年中，获得了几种线性时间解决方案。
Longest common subsequence (LCS) is one of the most fundamental problems in combinatorial optimization. Apart from theoretical importance, LCS has enormous applications in bioinformatics, revision control systems, and data comparison programs. Although a simple dynamic program computes LCS in quadratic time, it has been recently proven that the problem admits a conditional lower bound and may not be solved in truly subquadratic time. In addition to this, LCS is notoriously hard with respect to approximation algorithms. Apart from a trivial sampling technique that obtains a $n^{x}$ approximation solution in time $O(n^{2-2x})$ nothing else is known for LCS. This is in sharp contrast to its dual problem edit distance for which several linear time solutions are obtained in the past two decades.
