Approximating LCS in Linear Time: Beating the √n Barrier.

MohammadTaghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, Xiaorui Sun

Browse the full SODA paper archive.