The Computational Hardness of Estimating Edit Distance
From MaRDI portal
Publication:3068638
DOI10.1137/080716530zbMath1213.68305OpenAlexW2169838205MaRDI QIDQ3068638
Robert Krauthgamer, Alexandr Andoni
Publication date: 17 January 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1721.1/58102
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)
Related Items (6)
Sketching and Embedding are Equivalent for Norms ⋮ Unnamed Item ⋮ Estimating the Longest Increasing Sequence in Polylogarithmic Time ⋮ Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity ⋮ Adaptive metric dimensionality reduction ⋮ LCS Approximation via Embedding into Local Non-repetitive Strings
This page was built for publication: The Computational Hardness of Estimating Edit Distance
