Sequential and Parallel Approximation of Shortest Superstrings

✍ Scribed by Artur Czumaj; Leszek Gąsieniec; Marek Piotrów; Wojciech Rytter

• Book ID: 102578233
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 316 KB
• Volume: 23
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1996.0823

✦ Synopsis

Superstrings have many applications in data compression and genetics. However, the decision version of the shortest superstring problem is N N P P-complete. In this paper we examine the complexity of approximating shortest superstrings. There are two basic measures of the approximations: the length factor and the compression factor. The well known and practical approximation algorithm is the sequential algorithm GREEDY. It approximates the shortest superstring with the compression 1 Ž . factor of and with the length factor of 4. Our main results are: 1 A sequential 2 length approximation algorithm which achieves a length factor of 2.83. This result improves the best previously known bound of 2.