Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios

In the Shortest Superstring problem, we are given a set of strings and we are asking for a common superstring, having the minimum number of characters. This problem is NP-hard and several constant-factor approximation algorithms are known.

Of particular interest is the GREEDY algorithm, which repeatedly merges two strings of maximum overlap until one string remains.

We show that the approximation guarantee of GREEDY is at most 3.425. Furthermore, we prove that the Shortest Superstring can be approximated within a factor of 2.475.

This is joint work with Matthias Englert and Pavel Veselý.