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

Matthias Englert, Nicolaos Matsakis, Pavel Veselý

In the Shortest Superstring problem, we are given a set of strings and we are asking for a common superstring, which has the minimum number of characters. The Shortest Superstring…