Edit Distance with Multiple Block Operations†. (4th July 2018)

• Record Type: Journal Article
• Authors: Gonen, Mira; Shapira, Dana; Storer, James A
• Editors: Clifford, Raphael
• Is Part Of: Computer journal. Volume 62:Number 5(2019)
• Page Start: 657
• Page End: 669
• Publication Date: 2018-07-04
• Subjects: edit distance -- approximation algorithm -- constant factor approximation; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxy066
• Languages: English
• ISSNs: 0010-4620

Abstract

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 (Ergün, 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.