Edit Distance Approximation: Subquadratic Factor Three and Monge Approximation Schemes
The weighted edit distance $\mathsf{ed}^w(X,Y)$ is the minimum cost of an alignment of strings $X$ and $Y$, where a weight function $w$ specifies the cost of each character insertion, deletion, and substitution. For strings of total length $N$, the textbook dynamic program takes $O(N^2)$ time, and no $O(N^{2-\delta})$-...