arXiv:2610.01311 · v2
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-δ})$-time algorithm exists, even for unit costs, unless the Orthogonal Vectors Hypothesis (OVH) fails. This motivates the study of approximation algorithms. For unit costs and metric weights, the best truly subquadratic approximation factor was $3+\varepsilon$; we give randomized $3$-approximations in $\tilde O(N^{11/6})$ and $\tilde O(N^{40/21})$ time, respectively. For non-metric weights, we prove quadratic lower bounds for any approximation factor: $Ω(N^2)$ queries to $w$ over alphabets of size $Θ(N)$, and OVH-hardness over constant-size alphabets. These lower bounds motivate the bounded setting, parameterized by $k:=\mathsf{ed}^w(X,Y)$ for $w$ normalized so that every edit costs at least one. We give a deterministic $(1+\varepsilon)$-approximation algorithm in $\tilde O(N+k^2/\sqrt\varepsilon)$ time, matching the $O(N+k^2)$-time Landau-Vishkin algorithm for unit costs up to logarithmic factors for constant $\varepsilon>0$. Our main technical contribution is a Monge-matrix approximation framework for alignment problems: every $n\times n$ Monge matrix with entries in $\{0\}\cup[1,W]$ has an entrywise $(1+\varepsilon)$-approximation by a Monge matrix with $\tilde O(n\log(W)/\sqrt\varepsilon)$ strict Monge inequalities. As further applications of our Monge approximation framework, we maintain a $(1+\varepsilon)$-approximation of $\mathsf{ed}^w(X,Y)$ under character edits in $\tilde O(N\log(W)/\sqrt\varepsilon)$ time per update for weights at most $W$, and in $\tilde O(K/\sqrt\varepsilon)$ time for a fixed threshold $K$.
作者备注：Substantially extended version under a new title, adding the Monge approximation framework and its applications to bounded and dynamic weighted edit distance