Accurate and nearly optimal sublinear approximations to Ulam distance

DOI10.1137/1.9781611974782.131MaRDI QIDQ4575879zbMATH OpenOpenAlexFDO

Authors Timothy Naumovitz, C. Seshadhri, Michael Saks

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974782.131

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• Near-optimal sublinear time algorithms for Ulam distance
• Embedding the Ulam metric into \(\ell_{1}\)
• Approximating edit distance in near-linear time
• Polylogarithmic approximation for edit distance and the asymmetric query complexity
• Approximating edit distance in near-linear time

Cited in

(3)

• Near-optimal quantum algorithms for string problems
• Near-optimal sublinear time algorithms for Ulam distance
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems

This page was built for publication: Accurate and nearly optimal sublinear approximations to Ulam distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575879)