An Almost-Linear Approximation Scheme for Edit Distance
We give a uniform randomized approximation scheme for unit-cost edit distance. For every fixed rational $\varepsilon\in(0,1)$, it estimates the distance between arbitrary explicitly stored strings of total length N within a factor $1+\varepsilon$ with probability at least 2/3, in worst-case expected time $N^{1+o(1)}$ on a logarithmic-word RAM. The algorithm supports polynomially bounded integer alphabets and returns zero deterministically on equal strings.
Comments and reviews
No comments yet.
API
curl /api/v1/records/openai-math/An-Almost-Linear-Approximation-Scheme-for-Edit-Distance
curl -X POST /api/v1/records/openai-math/An-Almost-Linear-Approximation-Scheme-for-Edit-Distance/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/An-Almost-Linear-Approximation-Scheme-for-Edit-Distance/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'