Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity

摘要: We present a near-linear time algorithm that approximates the edit distance between two strings within polylogarithmic factor. For of length $n$ and every fixed $\eps>0$, computes $(\log n)^{O(1/\eps)}$ approximation in $n^{1+\eps}$ time. This is an {\em exponential} improvement over previously known factor, $2^{\tilde O(\sqrt{\log n})}$, with comparable running [Ostrovsky Rabani, J. ACM 2007, Andoni Onak, STOC 2009]. result arises naturally study new \emph{asymmetric query} model. In this model, input consists $x$ $y$, can access $y$ unrestricted manner, while being charged for querying symbol $x$. Indeed, we obtain our main by designing makes small number queries then provide nearly-matching lower bound on queries. Our first to expose hardness stemming from ``repetitive'', which means many their substrings are approximately identical. Consequently, provides rigorous separation Ulam distance.