Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance

DOI10.1137/1.9781611974782.131zbMath1411.68198OpenAlexW4231006448MaRDI QIDQ4575879

C. Seshadhri, Timothy Naumovitz, Michael E. 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)

Related Items (2)

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: Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance