On the Greedy Superstring Conjecture

We investigate the greedy algorithm for the shortest common superstring problem. For a restricted class of orders in which strings are merged, we show that the length of the greedy superstring is upperbounded by the sum of the length of an optimal superstring and an optimal cycle cover. Thus in this restricted setting we verify the well known conjecture, that the performance ratio of the greedy algorithm is within a factor of two of the optimum and actually extend the conjecture considerably. We achieve this by systematically..