A Strongly Subquadratic $(3+\epsilon )$-Approximation for Weighted Edit Distance over Arbitrary Metrics

We study weighted edit distance between two strings of total length $n$, where edit costs are induced by an arbitrary metric. For equal-length inputs, Kuszmaul (2019) gave an $O(n^{\delta })$-approximation with $\tilde{O}(n^{2-\delta })$ running time for every fixed $0<\delta <1$. We give the first constant-factor approximation for weighted edit distance over arbitrary metrics in strongly subquadratic running time. For every $0<\epsilon \le 1$, our randomized algorithm runs in $\tilde{O}(n^{7\mathrm{/}4}\mathrm{/}{\epsilon }^8)$ time and returns a $(3+\epsilon )$-approximation with probability at least $1-n^{-10}$. The algorithm allows unequal input lengths and places no bound on the ratio between edit costs.