Deterministic Longest Common Subsequence Approximation in Near-Linear Time

2025/07/30 by Boneh, Itai, Golan, Shay, Kraus, Matan
#Data Structures and Algorithms (cs.DS) #F.2.0 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2507.22486

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.

Citations

• A Linear-Time n^0.4-Approximation for Longest Common Subsequence
• Improved Dynamic Algorithms for Longest Increasing Subsequence
• Fully Dynamic Approximation of LIS in Polylogarithmic Time
• Edit Distance in Near-Linear Time: it's a Constant Factor
• Approximation Algorithms for LCS and LIS with Truly Improved Running Times
• Reducing approximate Longest Common Subsequence to approximate Edit Distance
• Approximating LCS in Linear Time: Beating the √(n) Barrier
• Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made
• Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping

Related

• A Linear-Time n^0.4-Approximation for Longest Common Subsequence
• Approximating LCS in Linear Time: Beating the √(n) Barrier
• Approximating the Longest Common Subsequence problem within a sub-polynomial factor in linear time
• Approximating binary longest common subsequence in almost-linear time
• A simple linear space algorithm for computing a longest common increasing subsequence