Publication
The Greedy Superstring Algorithm Achieves Ratio 2 for Strings of Length 6 Already
arXiv:2608.20018, 2026. PDF ยท Official record
Abstract
In the Shortest Common Superstring problem, one is given a set of strings and seeks a shortest string containing each input string as a substring. The longstanding greedy superstring conjecture states that repeatedly merging a pair of strings with maximum overlap gives a 2-approximation. Even for instances in which all strings have the same length (k), the exact approximation ratio was previously unknown for every (k geq 3).
We prove that strings of length six already suffice for the greedy algorithm to attain approximation ratio 2, and hence the ratio is at least 2 for every (k geq 6). We also completely characterize the length-three case, proving that its worst-case approximation ratio is (9/5).