Approximating LCS in Linear Time: Beating the √n Barrier

DOI10.1137/1.9781611975482.72zbMATH Open1431.68170arXiv2003.07285OpenAlexW2903274221MaRDI QIDQ5236256FDOQ5236256

Masoud Seddighin, S. Seddighin, Mohammad T. Hajiaghayi, Xiaorui Sun

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: Longest common subsequence (LCS) is one of the most fundamental problems in combinatorial optimization. Apart from theoretical importance, LCS has enormous applications in bioinformatics, revision control systems, and data comparison programs. Although a simple dynamic program computes LCS in quadratic time, it has been recently proven that the problem admits a conditional lower bound and may not be solved in truly subquadratic time. In addition to this, LCS is notoriously hard with respect to approximation algorithms. Apart from a trivial sampling technique that obtains a $n^x$ approximation solution in time $O(n^{2-2x})$ nothing else is known for LCS. This is in sharp contrast to its dual problem edit distance for which several linear time solutions are obtained in the past two decades.

Full work available at URL: https://arxiv.org/abs/2003.07285

Mathematics Subject Classification ID

Approximation algorithms (68W25) Algorithms on strings (68W32)

Cited In (7)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator
• Partial fillup and search time in LC tries
• A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence
• Near-optimal computation of runs over general alphabet via non-crossing LCE queries
• Longest common subsequence in sublinear space

   Recommendations

• Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrtTemplate:N$ Barrier 👍 👎
• Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds 👍 👎
• Polynomial-Time Approximation Algorithms for Weighted LCS Problem 👍 👎
• Polynomial-time approximation algorithms for weighted LCS problem 👍 👎
• A linear space algorithm for the LCS problem 👍 👎
• Approximability of Constrained LCS 👍 👎
• Approximability of constrained LCS 👍 👎
• Linear space streaming lower bounds for approximating CSPs 👍 👎
• Constrained LCS: Hardness and Approximation 👍 👎
• Quadratic-time algorithm for a string constrained LCS problem 👍 👎

This page was built for publication: Approximating LCS in Linear Time: Beating the √n Barrier

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236256)