RLE edit distance in near optimal time

05/03/2019
by   Raphael Clifford, et al.
0

We show that the edit distance between two run-length encoded strings of compressed lengths m and n respectively, can be computed in O(mn(mn)) time. This improves the previous record by a factor of O(n/(mn)). The running time of our algorithm is within subpolynomial factors of being optimal, subject to the standard SETH-hardness assumption. This effectively closes a line of algorithmic research first started in 1993.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset