On the Approximation Ratio of the Group-Merge Algorithm for the Shortest Common Superstring Problem

Abstract

The shortest common superstring problem (SCS) is one of the fundamental optimization problems in the area of data compression and DNA sequencing. The SCS is known to be APX-hard. This paper focuses on the analysis of the approximation ratio of two greedy-based approximation algorithms for it, namely the naive Greedy algorithm and the Group-Merge algorithm. The main results of this paper are:
I. We disprove the claim that the input instances of Jiang and Li {JL96} show that the Group-Merge algorithm does not provide any constant approximation for the SCS. We even prove that the Group-Merge algorithm always finds optimal solutions for these instances (except in one trivial case).
II. We show that the Greedy algorithm and the Group-Merge algorithm are incomparable according to the approximation ratio.