DocumentCode
2366834
Title
Approximating shortest superstrings
Author
Teng, Shang-Hua ; Yao, Frances
Author_Institution
Dept. of Math., MIT, Cambridge, MA, USA
fYear
1993
fDate
3-5 Nov 1993
Firstpage
158
Lastpage
165
Abstract
The Shortest Superstring Problem is to find a shortest possible string that contains every string in a given set as substrings. This problem has applications to data compression and DNA sequencing. As the problem is NP-hard and MAX SNP-hard, approximation algorithms are of interest. We present a new algorithm which always finds a superstring that is at most 2.89 times as long as the shortest superstring. Our result improves the 3-approximation result of Blum, Jiang, Li, Tromp, and Yannakakis (1991)
Keywords
algorithm theory; computational complexity; data compression; DNA sequencing; MAX SNP-hard; NP-hard; Shortest Superstring Problem; approximation algorithms; data compression; shortest superstrings; superstring; Approximation algorithms; DNA; Data compression; Greedy algorithms; Length measurement; Linear approximation; Mathematics; Polynomials;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1993. Proceedings., 34th Annual Symposium on
Conference_Location
Palo Alto, CA
Print_ISBN
0-8186-4370-6
Type
conf
DOI
10.1109/SFCS.1993.366871
Filename
366871
Link To Document