@article{9f8ca95a66934ebe8053b1c764967070,
title = "Approximating Edit Distance within Constant Factor in Truly Sub-quadratic Time",
abstract = "Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer, and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within approximation factor poly(log n). In this article, we provide an algorithm with running time {\~O}(n2-2/7) that approximates the edit distance within a constant factor.",
keywords = "Edit distance, approximation algorithm, randomized algorithm, sub-quadratic time algorithm",
author = "Diptarka Chakraborty and Debarati Das and Elazar Goldenberg and Michal Kouck{\'y} and Michael Saks",
note = "Funding Information: The research leading to these results is partially supported by the Grant Agency of the Czech Republic under Grant Agreement No. 19-27871X, by the European Research Council under the European Union{\textquoteright}s Seventh Framework Programme (FP/2007-2013)/ERC Grant Agreement No. 616787, and by the Simons Foundation under Grant No. 332622. Authors{\textquoteright} addresses: D. Chakraborty, School of Computing, National University of Singapore, 13 Computing Drive, Singapore, 117417, Singapore; email: diptarka@comp.nus.edu.sg; D. Das, University of Copenhagen, Universitetsparken 1, Copenhagen, 2100, Denmark; email: debaratix710@gmail.com; E. Goldenberg, The Academic College of Tel-Aviv-Yaffo, Rabenu Yeruham Street, Yaffo, 61083, Israel; email: elazargo@mta.ac.il; M. Kouck{\'y}, Charles University, Malostransk{\'e} n{\'a}m. 25, Prague, 11800, Czech Republic; email: koucky@iuuk.mff.cuni.cz; M. Saks, Department of Mathematics, Rutgers University, 110 Frelinghuysen Road, Piscataway, NJ, USA; email: msaks30@gmail.com. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. {\textcopyright} 2020 Association for Computing Machinery. 0004-5411/2020/10-ART36 $15.00 https://doi.org/10.1145/3422823 Publisher Copyright: {\textcopyright} 2020 ACM.",
year = "2020",
month = nov,
doi = "10.1145/3422823",
language = "English (US)",
volume = "67",
journal = "Journal of the ACM",
issn = "0004-5411",
publisher = "Association for Computing Machinery (ACM)",
number = "6",
}