Constant-factor approximation of near-linear edit distance in near-linear time

DOI10.1145/3357713.3384282OpenAlexW3034399032MaRDI QIDQ5144954

Aviad Rubinstein, Joshua Brakensiek

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.05390

zbMATH Keywords

approximation algorithmsrandomized algorithmsedit distance

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 approximation of near-linear edit distance in near-linear time