Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance
Timothy Naumovitz, Michael J. Saks, Comandur Seshadhri · 2017
The Ulam distance between two permutations of length η is the minimum number of insertions and deletions needed to transform one sequence into the other. Equivalently, the Ulam distance d is n minus the length of the longest common subsequence (LCS) between the permutations. Our main result is an algorithm, that for any fixed ∊ > 0, provides a (1 + ∊)-multiplicative approximation for d in time, which has been shown to be optimal up to polylogarithmic factors. This is the first sublinear time algorithm (provided that d = (log n)ω(1)) that obtains arbitrarily good multiplicative approximations to the Ulam distance. The previous best bound is an O(1)-approximation (with a large constant) by Andoni and Nguyen (2010) with the same running time bound (ignoring polylogarithmic factors). The improvement in the approximation factor from O(1) to (1 + ∊) allows for significantly more powerful sublinear algorithms. For example, for any fixed δ > 0, we can get additive δη approximations for the LCS between permutations in time. Previous sublinear algorithms require δ to be at least 1–1/C, where c is the approximation factor, which is close to 1 when c is large. Our algorithm is obtained by abstracting the basic algorithmic framework of Andoni and Nguyen, and combining it with the sublinear approximations for the longest increasing subsequence by Saks and Seshadhri (2010).