Approximating Shortest Superstrings

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). >

Authors

• Shang-Hua Teng
• F. Frances Yao

Keywords

• Approximation algorithms
• Polynomials
• Data compression
• DNA
• Mathematics
• Greedy algorithms
• Linear approximation
• Length measurement
• Source Code
• Estimation Algorithm
• Substring
• Estimation Strategy
• Backbone Structure
• Assignment Problem
• Approximate Ratio
• String Length
• Graph Metrics
• Performance Guarantees
• Optimal Assignment
• Cyclic Shift
• Total Overlap
• Hamiltonian Path