Metric Weighted Edit Distance: $(3+\epsilon )$-Approximation in ${\tilde{O}}_{\epsilon }(N^{1.6})$ Time

For every $0<\epsilon \le 1$, we give a randomized $(3+\epsilon )$-approximation to weighted edit distance when the costs form a metric on the alphabet augmented with a gap symbol. For strings of total length $N$, the running time is $\tilde{O}(N^{8\mathrm{/}5}\mathrm{/}{\epsilon }^{16\mathrm{/}5})$, where $\tilde{O}$ suppresses factors polynomial in $\log (N\mathrm{/}\epsilon )$. The dependence on $N$ matches that of the fastest known $(3+\epsilon )$-approximation for unit-cost edit distance. The algorithm never underestimates the edit distance and achieves the approximation guarantee with inverse-polynomial failure probability in $N$. The running time bound assumes constant-time exact arithmetic operations and metric queries, and it is independent of the numerical range of the edit costs. We build on three tools: the sampling framework of Chakraborty, Das, Goldenberg, Koucký, and Saks (J. ACM, 2020), with subsequent refinements by Andoni (2020); Kuszmaul’s removal of inexpensive characters (ICALP 2019); and Klein’s data structure for distances in planar graphs (SODA 2005). Our new ingredients include, among others, a decomposition of one string into pieces of bounded length with highly structured total deletion costs. This decomposition lets us compare all pieces against a small family of substrings of the other string.