Accurate and nearly optimal sublinear approximations to Ulam distance

DOI10.1137/1.9781611974782.131zbMATH Open1411.68198OpenAlexW4231006448MaRDI QIDQ4575879FDOQ4575879

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

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

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)

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)