On the Approximation Ratio of the Group-Merge Algorithm for the Shortest Common Superstring Problem
Dirk Bongartz
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
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.
Publié le : 2012-01-26
Classification: 
@article{cai527,
     author = {Dirk Bongartz},
     title = {On the Approximation Ratio of the Group-Merge Algorithm for the Shortest Common Superstring Problem},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai527}
}
Dirk Bongartz. On the Approximation Ratio of the Group-Merge Algorithm for the Shortest Common Superstring Problem. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai527/