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

(14)

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

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)