The shortest superstring problem is as follows: given a finite set of strings, find the shortest possible string s, such that every string in the set is a substring of s. Although this question is nondeterministic polynomial time (NP) hard, it is very important, due to its applications in different areas, like biology and data compression.

The algorithm analyzed is called GREEDY (due to the type of procedure used); it picks two strings (with some requirements fulfilled), and combines them into one string, which is then put back into the set. The method is reiterated until only one string remains.

In the paper by Blum et al. [1], two other variants are defined, MGREEDY and TGREEDY. If n denotes the length of the optimal superstring, a conjecture states that a GREEDY procedure produces a superstring of length at most 2n. However, all of the theoretical analyses constructed until now only guarantee an upper bound of 4n. In this paper, the authors prove an upper bound of 3.5n for the string produced by the GREEDY algorithm.