Abstrakt
The Shortest Superstring problem is an NP-hard problem, in which given as input a set of strings, we are looking for a string of minimum length that contains all input strings as substrings. The Greedy Conjecture (Tarhio and Ukkonen, 1988) states that the GREEDY algorithm, which repeatedly merges the two strings of maximum overlap, is 2-approximate.
We have recently shown (STOC 2022) that the approximation guarantee of GREEDY is at most 13+6SQUARE ROOT57 ALMOST EQUAL TO 3.425. Before that, the best established upper bound for this was 3.5 by Kaplan and Shafrir (IPL 2005), which improved upon the upper bound of 4 by Blum et al. (STOC 1991).
To derive our previous result, we established two incomparable upper bounds on the overlap sum of all cycle-closing edges in an optimal cycle cover and utilized lemmas of Blum et al. We improve the more involved one of the two bounds and, at the same time, make its proof more straightforward.
This results in an improved approximation guarantee of SQUARE ROOT67+23 ALMOST EQUAL TO 3.396 for GREEDY. Additionally, our result implies an algorithm for the Shortest Superstring problem having an approximation guarantee of SQUARE ROOT67+149 ALMOST EQUAL TO 2.466, improving slightly upon the previously best guarantee of SQUARE ROOT57+3718 ALMOST EQUAL TO 2.475 (STOC 2022).