Improved Approximation for Longest Common Subsequence over Small Alphabets

Understand

This paper investigates the approximability of the Longest Common Subsequence (LCS) problem.

• The fastest algorithm for solving the LCS problem exactly runs in essentially quadratic time in the length of the input, and it is known that under the Strong Exponential Time Hypothesis the quadratic running time cannot be beaten.
• There are no such limitations for the approximate computation of the LCS however, except in some limited scenarios.
• There is also a scarcity of approximation algorithms.