Approximating LCS in Linear Time: Beating the $\sqrt{n}$ Barrier

MohammadTaghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin +1

Longest common subsequence (LCS) is one of the most fundamental problems in combinatorial optimization. Apart from theoretical importance, LCS has enormous applications in bioinfor…