On the approximation ratio of the group-merge algorithm for the shortest common superstring problem

被引：0
|
作者：
Bongartz, D [1 ]
机构：
[1] Rhein Westfal TH Aachen, Lehrstuhl Informat 1, D-52074 Aachen, Germany
来源：
COMPUTING AND INFORMATICS | 2001年 / 20卷 / 04期
关键词：
shortest superstring problem; group-merge; approximation algorithm; DNA sequencing;
D O I：
暂无
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
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 [3]. 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 [9] 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 axe incomparable according to the approximation ratio.
引用
收藏
页码：325 / 357
页数：33
相关论文
共 15 条
  • [1] Why greed works for shortest common superstring problem
    Ma, Bin
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (51) : 5374 - 5381
  • [2] A Novel Approximation Algorithm for the Shortest Vector Problem
    Ajitha Shenoy, K. B.
    IEEE ACCESS, 2024, 12 : 141026 - 141031
  • [3] The shortest common superstring problem: Average case analysis for both exact and approximate matching
    Yang, EH
    Zhang, Z
    IEEE TRANSACTIONS ON INFORMATION THEORY, 1999, 45 (06) : 1867 - 1886
  • [4] A greedy approximation algorithm for the group Steiner problem
    Chekuri, C
    Even, G
    Kortsarz, G
    DISCRETE APPLIED MATHEMATICS, 2006, 154 (01) : 15 - 34
  • [5] Approximation algorithm for the group Steiner network problem
    Penn, Michal
    Rozenfeld, Stas
    NETWORKS, 2007, 49 (02) : 160 - 167
  • [6] The approximation ratio of the greedy algorithm for the metric traveling salesman problem
    Brecklinghaus, Judith
    Hougardy, Stefan
    OPERATIONS RESEARCH LETTERS, 2015, 43 (03) : 259 - 261
  • [7] An improved approximation algorithm for the minimum common integer partition problem
    Lin, Guohui
    Tong, Weitian
    INFORMATION AND COMPUTATION, 2021, 281
  • [8] An Improved Approximation Algorithm for the Shortest Link Scheduling Problem in Wireless Networks under SINR and Hypergraph Models
    Wang, Cui
    Yu, Jiguo
    Yu, Dongxiao
    Huang, Baogui
    WIRELESS ALGORITHMS, SYSTEMS, AND APPLICATIONS, WASA 2014, 2014, 8491 : 150 - 160
  • [9] APPROXIMATION ALGORITHM WITH CONSTANT RATIO FOR STOCHASTIC PRIZE-COLLECTING STEINER TREE PROBLEM
    Sun, Jian
    Sheng, Haiyun
    Sun, Yuefang
    DU, Donglei
    Zhang, Xiaoyan
    JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2021, 18 (05) : 3351 - 3363
  • [10] An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties
    Zhang, Jiaxuan
    Gao, Suogang
    Hou, Bo
    Liu, Wen
    COMPUTATIONAL & APPLIED MATHEMATICS, 2022, 41 (06)
12