Skip to content
Preprint

Edit Distance Approximation: Subquadratic Factor Three and Monge Approximation Schemes

Oct 2026 · 2 citations
Computer Science

Abstract

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})$-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: $\Omega(N^2)$ queries to $w$ over alphabets of size $\Theta(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$.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.