Name
Abstract | ||
|---|---|---|
In this paper, we consider the edit distance with block moves, block copies and block deletions, which is shown to be NP-hard, and employ a simple left-to-right greedy sliding window algorithm that achieves a constant factor approximation ratio of 5. This is an improvement on the constant approximation of 12 presented by Ergun and Sahinalp (Ergun, F., Muthukrishnan, S., and Sahinalp, S. C. Comparing sequences with segment rearrangements. FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science), and is achieved by a proof that introduces two non-trivial kinds of substrings for different purposes, so recursive and non-recursive operations can be treated at the same time. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1093/comjnl/bxy066 | COMPUTER JOURNAL |
Keywords | Field | DocType |
edit distance,approximation algorithm,constant factor approximation | Edit distance,Computer science,Theoretical computer science | Journal |
Volume | Issue | ISSN |
62 | 5 | 0010-4620 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mira Gonen | 1 | 78 | 11.05 |
| Dana Shapira | 2 | 144 | 32.15 |
| James A. Storer | 3 | 931 | 156.06 |