Bringmann, Karl ;
Das, Debarati
A LinearTime n^{0.4}Approximation for Longest Common Subsequence
Abstract
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 constantfactor approximation in almostlinear 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 Õ(n^{2ε}) has been known, for any constant 0 < ε ≤ 1. Recently, a breakthrough result by Hajiaghayi, Seddighin, Seddighin, and Sun [SODA'19] provided a lineartime algorithm that yields a O(n^{0.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(n^{2ε}) computes an Õ(n^{2ε/5})approximation with high probability, for any 0 < ε ≤ 1. Our result (1) gives an Õ(n^{0.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(n^{2ε}), improving upon the naive bound of O(n^{ε/2}) for any ε, and (3) instead of only in expectation, succeeds with high probability.
BibTeX  Entry
@InProceedings{bringmann_et_al:LIPIcs.ICALP.2021.39,
author = {Bringmann, Karl and Das, Debarati},
title = {{A LinearTime n^\{0.4\}Approximation for Longest Common Subsequence}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {39:139:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14108},
URN = {urn:nbn:de:0030drops141082},
doi = {10.4230/LIPIcs.ICALP.2021.39},
annote = {Keywords: approximation algorithm, longest common subsequence, string algorithm}
}
02.07.2021
Keywords: 

approximation algorithm, longest common subsequence, string algorithm 
Seminar: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Issue date: 

2021 
Date of publication: 

02.07.2021 