arXiv preprint ·
Factor Three Approximation for Edit Distance
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We give randomized algorithms for $3$-approximate edit distance in $\widetilde{\mathcal{O}}(N^{11/6})$ time for unweighted edit distance and in $\widetilde{\mathcal{O}}(N^{40/21})$ time for arbitrary metric edit weights, where $N$ is the total input length. For non-metric costs, we prove an unconditional $Ω(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. This holds even for symmetric weights over a size-$3$ alphabet or triangle-inequality weights over a size-$2$ alphabet. In contrast, for symmetric weights over a binary alphabet we show an $\widetilde{\mathcal{O}}(N^{40/21})$-time $3$-approximation algorithm.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Sparsification Framework for Directed Densest Subgraph
A Shortest Augmenting Path Algorithm for Linear Matroid Parity
Beyond odd characteristic: Faster isomorphism testing of 2-groups of Frattini class 2
Hamiltonian locality testing and certification do not achieve the Heisenberg limit
A Faster Auction Algorithm for Weighted Matroid Intersection
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.