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.
Downloads
Download data is not yet available.
Published
2012-02-21
How to Cite
Bongartz, D. (2012). On the Approximation Ratio of the Group-Merge Algorithm for the Shortest Common Superstring Problem. Computing and Informatics, 20(4), 325–357. Retrieved from http://147.213.75.17/ojs/index.php/cai/article/view/527
Issue
Section
Articles