A linear-time n0.4-approximation for longest common subsequence

Karl Bringmann, Debarati Das

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


We consider the classic problem of computing the Longest Common Subsequence (LCS) of two strings of length n. While a simple quadratic algorithm has been known for the problem for more than 40 years, no faster algorithm has been found despite an extensive effort. The lack of progress on the problem has recently been explained by Abboud, Backurs, and Vassilevska Williams [FOCS'15] and Bringmann and Künnemann [FOCS'15] who proved that there is no subquadratic algorithm unless the Strong Exponential Time Hypothesis fails. This major roadblock for getting faster exact algorithms has led the community to look for subquadratic approximation algorithms for the problem. Yet, unlike the edit distance problem for which a constant-factor approximation in almost-linear time is known, very little progress has been made on LCS, making it a notoriously difficult problem also in the realm of approximation. For the general setting (where we make no assumption on the length of the optimum solution or the alphabet size), only a naive O(n∈/2)-approximation algorithm with running time Õ(n2-∈) has been known, for any constant 0 < ∈ ≤ 1. Recently, a breakthrough result by Hajiaghayi, Seddighin, Seddighin, and Sun [SODA'19] provided a linear-time algorithm that yields a O(n0.497956)-approximation in expectation; improving upon the naive O(√ n)-approximation for the first time. In this paper, we provide an algorithm that in time O(n2-∈) computes an Õ(n2∈/5)-approximation with high probability, for any 0 < ∈ ≤ 1. Our result (1) gives an Õ(n0.4)-approximation in linear time, improving upon the bound of Hajiaghayi, Seddighin, Seddighin, and Sun, (2) provides an algorithm whose approximation scales with any subquadratic running time O(n2-∈), improving upon the naive bound of O(n∈/2) for any ∈, and (3) instead of only in expectation, succeeds with high probability.

Original languageEnglish (US)
Title of host publication48th International Colloquium on Automata, Languages, and Programming, ICALP 2021
EditorsNikhil Bansal, Emanuela Merelli, James Worrell
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771955
StatePublished - Jul 1 2021
Event48th International Colloquium on Automata, Languages, and Programming, ICALP 2021 - Virtual, Glasgow, United Kingdom
Duration: Jul 12 2021Jul 16 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference48th International Colloquium on Automata, Languages, and Programming, ICALP 2021
Country/TerritoryUnited Kingdom
CityVirtual, Glasgow

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'A linear-time n0.4-approximation for longest common subsequence'. Together they form a unique fingerprint.

Cite this