TY - JOUR

T1 - A Linear-Time n0.4-Approximation for Longest Common Subsequence

AU - Bringmann, Karl

AU - Cohen-Addad, Vincent

AU - Das, Debarati

N1 - Publisher Copyright:
© 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM.

PY - 2023/2/20

Y1 - 2023/2/20

N2 - We consider the classic problem of computing the Longest Common Subsequence (LCS) of two strings of length n. The 40-year-old quadratic-time dynamic programming algorithm has recently been shown to be near-optimal by Abboud, Backurs, and Vassilevska Williams [FOCS'15] and Bringmann and Künnemann [FOCS'15] assuming the Strong Exponential Time Hypothesis. This 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, only a naive O(nI/2-approximation algorithm with running time OŠ(n2-I has been known, for any constant 0 < I ≤ 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 -approximation for the first time.In this paper, we provide an algorithm that in time O(n2-I) computes an OŠ(n2/5-approximation with high probability, for any 0 < I ≤ 1. Our result (1) gives an OŠ(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-I), improving upon the naive bound of O(nI/2) for any I, and (3) instead of only in expectation, succeeds with high probability.

AB - We consider the classic problem of computing the Longest Common Subsequence (LCS) of two strings of length n. The 40-year-old quadratic-time dynamic programming algorithm has recently been shown to be near-optimal by Abboud, Backurs, and Vassilevska Williams [FOCS'15] and Bringmann and Künnemann [FOCS'15] assuming the Strong Exponential Time Hypothesis. This 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, only a naive O(nI/2-approximation algorithm with running time OŠ(n2-I has been known, for any constant 0 < I ≤ 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 -approximation for the first time.In this paper, we provide an algorithm that in time O(n2-I) computes an OŠ(n2/5-approximation with high probability, for any 0 < I ≤ 1. Our result (1) gives an OŠ(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-I), improving upon the naive bound of O(nI/2) for any I, and (3) instead of only in expectation, succeeds with high probability.

UR - http://www.scopus.com/inward/record.url?scp=85176766068&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85176766068&partnerID=8YFLogxK

U2 - 10.1145/3568398

DO - 10.1145/3568398

M3 - Article

AN - SCOPUS:85176766068

SN - 1549-6325

VL - 19

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 1

M1 - 3568398

ER -