  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.
