Metraipolis › archive › dc_9c129cd07627
A Strongly Subquadratic $(3+\varepsilon)$-Approximation for Weighted Edit Distance over Arbitrary Metrics — arXiv:2609.14873
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.14873
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T02:15:27.756Z
- SHA-256 of the archived text
bc385be653411bdb5516acc8926e50addd7a9cc55bdd334ff42eac8d0d3f6c06- Stable URL of this page
https://metraipolis.com/documento/dc_9c129cd07627
How to cite
A Strongly Subquadratic $(3+\varepsilon)$-Approximation for Weighted Edit Distance over Arbitrary Metrics — arXiv:2609.14873 — arXiv (en), https://arxiv.org/abs/2609.14873 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9c129cd07627 (Metraipolis archive dc_9c129cd07627, sha256 bc385be653411bdb5516acc8926e50addd7a9cc55bdd334ff42eac8d0d3f6c06)
BibTeX
@misc{dc9c129cd07627,
title = {A Strongly Subquadratic $(3+varepsilon)$-Approximation for Weighted Edit Distance over Arbitrary Metrics — arXiv:2609.14873},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.14873},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9c129cd07627; sha256 bc385be653411bdb5516acc8926e50addd7a9cc55bdd334ff42eac8d0d3f6c06},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.14873. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study weighted edit distance between two strings of total length $n$, where edit costs are induced by an arbitrary metric. For equal-length inputs, Kuszmaul (2019) gave an $O(n^\delta)$-approximation with $\widetilde{O}(n^{2-\delta})$ running time for every fixed $0 < \delta < 1$. We give the first constant-factor approximation for weighted edit distance over arbitrary metrics in strongly subquadratic running time. For every $0 < \varepsilon \le 1$, our randomized algorithm runs in $\widetilde{O}(n^{7/4}/\varepsilon^8)$ time and returns a $(3+\varepsilon)$-approximation with probability at least $1-n^{-10}$. The algorithm allows unequal input lengths and places no bound on the ratio between edit costs.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.14873 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T01:54:07.130Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).