Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time

DOI10.1145/3422823zbMath1499.68420arXiv1810.03664OpenAlexW3097495782MaRDI QIDQ5056449

Michal Koucký, Debarati Das, Diptarka Chakraborty, Elazar Goldenberg, Michael E. Saks

Publication date: 8 December 2022

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmrandomized algorithmedit distancesub-quadratic-time algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation algorithms (68W25) Randomized algorithms (68W20) Algorithms on strings (68W32)

Related Items (5)

Weak inverse neighborhoods of languages ⋮ A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence ⋮ Quantum bounds for 2D-grid and Dyck language ⋮ Near-optimal quantum algorithms for string problems ⋮ Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems

This page was built for publication: Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time