Edit Distance Approximation: Subquadratic Factor Three and Monge Approximation Schemes

arXiv:2610.01311 · cs.DS · Submitted 2026-10-01 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Edit Distance Approximation".

Jane: Here's the gist of the paper. We give randomized algorithms for 3-approximate edit distance in Oe(N(11/6)) time for unweighted edit distance and in Oe(N(40/21)) time for arbitrary metric edit weights, where N is the total input length For non-metric costs, we prove an unconditional omega(N 2) oracle-query lower bound for every approximation factor depending only on N, even for symmetric weights or weights satisfying the triangle inequality (but not both) Under the Orthogonal Vectors Hypothesis, we show a similar result for constant-size alphabets In contrast, for symmetric weights over a binary alphabet we show an Oe(N(40/21)) time 3-approximation algorithm.

Tom: Factor Three Approximation for Unit Costs The unit-cost approximation algorithm achieves a factor three guarantee with no additive error in Oe((n + m)(11/6)) time This is achieved by partitioning the source string X into consecutive substrings Ui, called source blocks, of length at most W = o(N) each.

Jane: The algorithm uses a routing idea where it computes distances from a small set C of intermediate strings called centers to all source blocks Ui and all substrings of Y.

Tom: By using the triangle inequality of edit distance, it claims that ed(Ui, Y[p..

Paper summary: Tom: So, to wrap up this discussion on "Edit Distance Approximation: Subquadratic Factor Three and Monge Approximation Schemes", this paper presents randomized algorithms that give a factor three approximation for edit distance. They achieve big O of N eleven six over twelve time for unweighted edit distance and big O of N forty over twenty-one time for arbitrary metric weights.

Jane: The title itself points to the two main contributions: the subquadratic factor three approximation and the monge approximation schemes they introduce. Essentially, they figured out a way to use routing ideas with centers to get those good approximations in better than quadratic time when things aren't just simple character edits.

Lu: What this means for the world is that we can now handle more complex distance measures, like weighted costs, without immediately jumping into algorithms that take time scaling quadratically with the size of the strings. This opens up possibilities for sequence alignment in real-world bioinformatics or even complex data comparison tasks where errors aren't uniform.

Meng: From an engineering standpoint, it gives us a concrete path to deploying approximate solutions for metric edit distance on large datasets, provided we can manage that N forty over twenty-one runtime. It’s a specific performance target we can aim for in our development pipeline.

Tom: Exactly, and the paper also sets important lower bounds on the oracle query complexity, showing that without certain cost structures like symmetry or triangle inequality, you still face quadratic time hurdles for finding good approximations. That tells us what's fundamentally impossible without those structural assumptions.

Jane: So the paper gives us a very specific toolkit for balancing speed and accuracy in approximate edit distance, showing concrete runtime bounds and where the limitations of those tools lie when the cost functions aren't perfectly behaved.

Conclusion: Tom: So we're wrapping up on this paper about "Edit Distance Approximation: Subquadratic Factor Three and Monge Approximation Schemes." It tackles how to get a good estimate of edit distance without needing a quadratic amount of time for huge strings.

Jane: Right, so they’ve got these randomized algorithms, right? They use some clever ideas involving partitioning the source string into blocks and using these intermediate centers to get an approximation that’s only three times the true distance.

Lu: That factor three approximation is achieved in time that scales like N eleven six over twelve for unweighted edit distance. It uses this routing idea where you compute distances from a few specific centers to all the parts of your target string.

Meng: For me, the real thing is that it handles metric costs too, not just simple character matches. The time complexity jumps up to N forty over twenty-one for those more complicated weight functions, which is still pretty manageable for production at scale.

Lalam: What they're showing here is that we can get a three times approximation with these specific runtime guarantees when you move past the simplest edit distance problems into things where the costs matter.

Tom: So what does this mean for us? It means we can handle more complex data comparisons on massive datasets without immediately hitting a wall of quadratic time.

Jane: It suggests that for many practical applications, especially in areas like bioinformatics where sequences are long, we don't have to settle for just a rough guess anymore.

Lu: The lower bounds they set are important too. They show that if you don't have certain mathematical properties on your costs—like symmetry or the triangle inequality—you can expect to face quadratic time hurdles again for these approximations.

Meng: That tells me we need to be careful about what kind of cost functions we choose for our real data, because if they don't fit those nice properties, the speed advantage disappears.

Tom: So basically, they give us a concrete tool that works well under specific conditions but warn us where those conditions are important for the performance to hold up.

Jane: And that leads into what’s next: we need to dig into those lower bounds and see exactly how much faster we can go if we relax some of those requirements.

ETH Zurich · Max Planck Institute for Informatics

cs.DS

Submitted: 2026-10-01

Updated: 2026-11-10

Comments: Substantially extended version under a new title, adding the Monge approximation framework and its applications to bounded and dynamic weighted edit distance

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 72/100

The gist: We give randomized algorithms for 3-approximate edit distance in Oe(N(11/6)) time for unweighted edit distance and in Oe(N(40/21)) time for arbitrary metric edit weights…

Key concepts

Unit-Cost Approximation
This method guarantees a factor three approximation with no additive error in Oe((n + m)^(11/6)) time. It works by dividing the source string into smaller blocks and using a routing strategy based on intermediate 'centers' to estimate distances between blocks and target substrings, leveraging the triangle inequality of edit distance.
Metric-Weighted Approximation
This algorithm finds an alignment for strings with arbitrary metric costs in Oe((n + m)^(40/21)) time. It combines the center-correcting idea with DIST-matrix machinery to efficiently reuse preprocessing, allowing it to achieve a 3-approximation for weighted edit distances with high probability.
Source Blocks and Centers
The source string is partitioned into consecutive 'source blocks' of limited length. A small set of 'centers' strings are computed against these blocks and target substrings. This partitioning allows the algorithm to use localized distance estimates, simplifying the overall computation by avoiding full preprocessing against the entire target string.
Hardness Results
The paper establishes lower bounds showing that achieving certain approximation factors for non-metric costs requires a high number of oracle queries (Ω(N^2)). For constant-size alphabets, it uses the Orthogonal Vectors Hypothesis to show no faster than O(N^(2-δ)) time algorithm exists for symmetric weights.

Terminology

Summary

We give randomized algorithms for 3-approximate edit distance in Oe(N(11/6)) time for unweighted edit distance and in Oe(N(40/21)) time for arbitrary metric edit weights, where N is the total input length For non-metric costs, we prove an unconditional omega(N 2) oracle-query lower bound for every approximation factor depending only on N, even for symmetric weights or weights satisfying the triangle inequality (but not both) Under the Orthogonal Vectors Hypothesis, we show a similar result for constant-size alphabets In contrast, for symmetric weights over a binary alphabet we show an Oe(N(40/21)) time 3-approximation algorithm. p. 0

Factor Three Approximation for Unit Costs

The unit-cost approximation algorithm achieves a factor three guarantee with no additive error in Oe((n + m)(11/6)) time This is achieved by partitioning the source string X into consecutive substrings Ui, called source blocks, of length at most W = o(N) each. The algorithm uses a routing idea where it computes distances from a small set C of intermediate strings called centers to all source blocks Ui and all substrings of Y. p. 1 By using the triangle inequality of edit distance, it claims that ed(Ui, Y[p. p. 0. q)) ≤ ri + ed(Ci, Y[p.. q)) ≤ ed(Ui, Y[p.. q)) + 2ri. The single corrected edit in the center Ci is different for each source block Ui, but it does not require separate preprocessing against the entire target string Y. p. 1

Metric-Weighted Approximation

For arbitrary metric costs, there is a randomized algorithm that runs in Oe((n + m)(40/21)) time and returns an alignment A of X onto Y of weighted cost Db such that Db ≤ 3edw(X, Y) holds with high probability. This algorithm pairs metric tools with the center-correcting idea, replacing some substring of the center by a short substring of the source block Ui. p. 2 The same DIST-matrix machinery from the unit-cost case allows for efficient reuse of preprocessing for the centers. p. 2

Where the gains come from

The time complexity is derived by setting W:= ceil(N(1/6)), k:= ceil(N(1/3)), and η:= 1/W, which yields a total time complexity of Oe(N(11/6)). The exact shortcut search involves building a balanced binary tree on the ordered source block indices [0. p. 9. R] and sampling source blocks based on their positive radius ri > 0. p. 9 The final time complexity is Oe(N(40/21)). p. 0

Hardness Results

The paper establishes several lower bounds, including an oracle-based lower bound for large alphabets requiring omega(N 2) oracle queries in expectation. For a constant-size alphabet, it uses the Orthogonal Vectors Hypothesis (OVH) to show no O(N(2-δ)) time algorithm exists for symmetric weight functions. p. 0 Furthermore, it proves that binary alphabet quasimetric hardness occurs without symmetry. p. 3

Open Questions

The paper highlights several open questions regarding the tradeoff between running time and approximation, such as obtaining a (3 - ε)-approximation in truly subquadratic time. It also questions whether faster exponents like N(8/5+o(1)) can be achieved for factors just above three. p. 4 p. 4 Finally, it asks about the existence of a deterministic constant-factor approximation in almost-linear time. p. 4 p. 4

The paper highlights several open questions regarding the tradeoff between running time and approximation, such as obtaining a (3 - ε)-approximation in truly subquadratic time for some absolute constant ε > 0. It also questions whether faster exponents like N(8/5+o(1)) can be achieved for factors just above three. Finally, it asks about the existence of a deterministic constant-factor approximation in almost-linear time.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved Edit Distance Approximation for Unweighted Costs: The system can compute an alignment A of strings X onto Y of unweighted cost Db such that Db less than or equal to 3ed(X, Y) with high probability in Oe ((n + m) 11/6) time.

  2. Improved Metric-Weighted Edit Distance Approximation: For arbitrary metric weights w, the system can return an alignment A of X onto Y of weighted cost Db such that Db less than or equal to 3edw(X, Y) with high probability in Oe ((n + m) 40/21) time.

  3. Faster Subquadratic Approximation for Metric Edit Distance: The system achieves a (3 + epsilon)-approximation in Oe (N7/4/epsilon8) time for arbitrary metric costs, representing a significant improvement over previous bounds.

  4. Efficient Processing of String Alignments: The system can process the alignment graph using certified shortcuts and routing shortcuts to compute distances in truly subquadratic time by partitioning the source string X into source blocks Ui of length at most W = o(N) each.

  5. Constant-Factor Approximation for Binary Symmetric Weights: For binary alphabets, the system can achieve a (3 + epsilon)-approximation in Oe ((n + m) 40/21) time even with a symmetric weight function w over size-3 alphabet or triangle-inequality weights over size-2 alphabet.

  6. Hardness Analysis for Exact Computation: The system can utilize oracle lower bounds to prove that every randomized algorithm requiring worst-case running time O(N2 minus delta) cannot compute exact weighted edit distance in subquadratic time, even under symmetric or triangle inequality assumptions.

Sources

Related papers