Deterministic Longest Common Subsequence Approximation in Near-Linear Time

Abstract

We provide a deterministic algorithm that outputs an $O(n^{3/4}\log n)$-approximation for the Longest Common Subsequence (LCS) of two input sequences of length $n$ in near-linear time. This is the first deterministic approximation algorithm for LCS that achieves a sub-linear approximation ratio in near-linear time.