Constant factor approximations to edit distance on far input pairs in nearly linear time

DOI10.1145/3357713.3384307OpenAlexW3034952850MaRDI QIDQ5144955

Michal Koucký, Michael E. Saks

Publication date: 19 January 2021

Published in: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmrandomized algorithmedit distancealmost linear-time algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (3)

Longest common subsequence in sublinear space ⋮ A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence ⋮ Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems

This page was built for publication: Constant factor approximations to edit distance on far input pairs in nearly linear time