{"ID":23507445,"CreatedAt":"2026-09-18T02:21:44.056544415Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.20796","arxiv_id":"2609.20796","title":"Metric Weighted Edit Distance: $(3+\\varepsilon)$-Approximation in $\\widetilde O_\\varepsilon(N^{1.6})$ Time","abstract":"For every $0 \u003c \\varepsilon \\le 1$, we give a randomized $(3+\\varepsilon)$-approximation to weighted edit distance when the costs form a metric on the alphabet augmented with a gap symbol. For strings of total length $N$, the running time is $\\widetilde{O}(N^{8/5}/\\varepsilon^{16/5})$, where $\\widetilde{O}$ suppresses factors polynomial in $\\log(N/\\varepsilon)$. The dependence on $N$ matches that of the fastest known $(3+\\varepsilon)$-approximation for unit-cost edit distance. The algorithm never underestimates the edit distance and achieves the approximation guarantee with inverse-polynomial failure probability in $N$. The running time bound assumes constant-time exact arithmetic operations and metric queries, and it is independent of the numerical range of the edit costs. We build on three tools: the sampling framework of Chakraborty, Das, Goldenberg, Koucký, and Saks (J. ACM, 2020), with subsequent refinements by Andoni (2020); Kuszmaul's removal of inexpensive characters (ICALP 2019); and Klein's data structure for distances in planar graphs (SODA 2005). Our new ingredients include, among others, a decomposition of one string into pieces of bounded length with highly structured total deletion costs. This decomposition lets us compare all pieces against a small family of substrings of the other string.","short_abstract":"For every $0 \u003c \\varepsilon \\le 1$, we give a randomized $(3+\\varepsilon)$-approximation to weighted edit distance when the costs form a metric on the alphabet augmented with a gap symbol. For strings of total length $N$, the running time is $\\widetilde{O}(N^{8/5}/\\varepsilon^{16/5})$, where $\\widetilde{O}$ suppresses f...","url_abs":"https://arxiv.org/abs/2609.20796","url_pdf":"https://arxiv.org/pdf/2609.20796v1","authors":"[\"Debarati Das\",\"Evangelos Kipouridis\",\"Tomasz Kociumaka\"]","published":"2026-09-17T17:54:31Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}