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, which has the minimum number of characters. The Shortest Superstring problem is NP-hard and several constant-factor approximation algorithms are known for it. Of particular interest is the Greedy algorithm, which repeatedly merges two strings of maximum overlap until a single string remains. Tarhio and Ukkonen (TCS 1988) conjectured that Greedy is 2-approximate. In a seminal work, Blum, Jiang, Li, Tromp, and Yannakakis (STOC 1991) proved that the superstring computed by Greedy is a 4-approximation, and this upper bound was improved to 3.5 by Kaplan and Shafrir (IPL 2005). We show that the approximation guarantee of Greedy is at most √ 67+2 3 ≈ 3.396. Furthermore, we prove that the Shortest Superstring can be approximated within a factor of √ 67+14 9 ≈ 2.466, improving slightly upon the currently best 2 11 23 -approximation algorithm by Mucha (SODA 2013).