Abstract
We consider the problem of obtaining approximation algorithms for standard edit distance and Dyck edit distance that are simple, deterministic and fast, but whose approximation factor may be high. For the standard edit distance of two strings, we introduce a class of simple and fast algorithms called \emph{basic single pass algorithms}. Saha (2014) gave a randomized algorithm in this class that achieves an $O(d)$ approximation on inputs $x,y$ whose edit distance is $O(d)$. In this paper, we (1) present a deterministic algorithm in this class that achieves similar performance and (2) prove that no algorithm (even randomized) in this class can give a better approximation factor. For the Dyck edit distance problem, Saha gave a randomized reduction from Dyck edit distance to standard two string edit distance at a cost of a $O(\log d)$ factor where $d$ is the Dyck edit distance. We give a deterministic reduction whose description and proof are very simple.