D. Das

Metric Weighted Edit Distance: $(3+\varepsilon)$-Approximation in $\widetilde O_\varepsilon(N^{1.6})$ Time

For every $0<\varepsilon \le 1$, we give a randomized $(3+\varepsilon)$-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 $\widetilde{O}(N^{8/5}/\varepsilon^{16/5})$, where $\widetilde{O}$ suppresses fac...