APPROXIMATING LONGEST COMMON SUBSEQUENCE IN LINEAR TIME: BEATING THE √n BARRIER.

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 [2, 18]. In addition to this, LCS is notoriously hard with respect to approximation algorithms. Apart from a trivial sampling technique that obtains an nx approximation solution in time O(n2-2x) nothing else is known for LCS. This is in sharp contrast to its dual problem edit distance, for which several linear time solutions were obtained in the past two decades [5, 6, 10, 11, 19]. In this work, we present the first nontrivial algorithm for approximating LCS in linear time. Our main result is a linear time algorithm for the LCS which has an approximation factor of O(n0.4991319) in expectation. This beats the √n barrier for approximating LCS in linear time. [ABSTRACT FROM AUTHOR]