Approximation Algorithms for LCS and LIS with Truly Improved Running Times

Understand

Longest common subsequence ($\mathsf{LCS}$) is a classic and central problem in combinatorial optimization.

• While $\mathsf{LCS}$ admits a quadratic time solution, recent evidence suggests that solving the problem may be impossible in truly subquadratic time.
• A special case of $\mathsf{LCS}$ wherein each character appears at most once in every string is equivalent to the longest increasing subsequence problem ($\mathsf{LIS}$) which can be solved in quasilinear time.
• In this work, we present novel algorithms for approximating $\mathsf{LCS}$ in truly subquadratic time and $\mathsf{LIS}$ in truly sublinear time.