Approximating LCS in Linear Time: Beating the √n Barrier

DOI10.1137/1.9781611975482.72MaRDI QIDQ5236256zbMATH OpenOpenAlexFDO

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

Publication date 15 October 2019

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

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

Mathematics Subject Classification ID

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

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.

Recommendations

• Approximating longest common subsequence in linear time: beating the \(\sqrt{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

Cited in

(18)

• Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
• scientific article; zbMATH DE number 7539923 (Why is no real title available?)
• LCS Approximation via Embedding into Local Non-repetitive Strings
• Massively parallel approximation algorithms for edit distance and longest common subsequence
• scientific article; zbMATH DE number 7758340 (Why is no real title available?)
• Approximability of constrained LCS
• Approximability of constrained LCS
• Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator
• LCS approximation via embedding into locally non-repetitive strings
• Improved approximation for longest common subsequence over small alphabets
• A linear-time \(n^{0.4}\)-approximation for longest common subsequence
• Streaming and small space approximation algorithms for edit distance and longest common subsequence
• A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence
• Towards hardness of approximation for polynomial time problems
• Near-optimal computation of runs over general alphabet via non-crossing LCE queries
• Approximation algorithms for LCS and LIS with truly improved running times
• Longest common subsequence in sublinear space
• Approximating longest common subsequence in linear time: beating the \(\sqrt{n}\) barrier

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)