Lesson 7

As we mentioned earlier, no polynomial-time exact algorithms for the superstring problem are known. However, there are actively studied approximate algorithms: an \(\alpha\)-approximation algorithm in polynomial time finds a superstring that is guaranteed to be no more than \(\alpha\) times longer than the optimal superstring. The best result so far is \(\alpha \approx 2{,}466\) (obtained by Englert, Matsakis and Veselý in 2023). The corresponding algorithm and its analysis are relatively complex: they use graph techniques and combinatorics on words.

At the same time, for over forty years, the following greedy hypothesis has remained open. Consider the following natural greedy algorithm, which takes as input a set of strings \(S\):

1. while there are at least two strings in \(S\):
   1. \(s,t \gets \text{two strings from \(S\) with the maximum \(\operatorname{overlap}(s,t)\)}\)
   2. replace in \(S\) the strings \(s\) and \(t\) with \(\operatorname{superstring}(s,t)\)
2. return the only string from \(S\)

As you can see, this is a very simple algorithm. It is known that it can be implemented in linear (in terms of the sum of the lengths of the input strings) time. The greedy hypothesis asserts that this algorithm is a \(2\)-approximation algorithm, whereas the best currently proven approximation ratio is \(3{,}396\). Proving this hypothesis would solve three problems:

1. Solve an open problem that has been unresolved for over forty years!
2. Show that a very simple algorithm can provide guaranteed approximation!
3. Improve all known approximation guarantees!