Approximating Edit Distance in Near-Linear Time

DOI10.1137/090767182zbMath1261.68067arXiv1109.5635OpenAlexW2019972981MaRDI QIDQ4910578

Krzysztof Onak, Alexandr Andoni

Publication date: 19 March 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsedit distancemetric embeddings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorics on words (68R15) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (6)

A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence ⋮ Unnamed Item ⋮ Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ Unnamed Item ⋮ Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation

This page was built for publication: Approximating Edit Distance in Near-Linear Time