The smoothed complexity of edit distance

DOI10.1145/2344422.2344434zbMath1295.68206OpenAlexW2076238476MaRDI QIDQ3189087

Alexandr Andoni, Robert Krauthgamer

Publication date: 9 September 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2344422.2344434

zbMATH Keywords

linear timeedit distancesublinear timesmooth complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)

Related Items (3)

The Complexity of Problems in P Given Correlated Instances ⋮ Smoothed Analysis of Local Search Algorithms ⋮ Estimating the Longest Increasing Sequence in Polylogarithmic Time

This page was built for publication: The smoothed complexity of edit distance