Reoptimization of the shortest common superstring problem (Q639296): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Set OpenAlex properties.
Property / OpenAlex ID
 
Property / OpenAlex ID: W2031907835 / rank
 
Normal rank

Revision as of 22:26, 19 March 2024

scientific article
Language Label Description Also known as
English
Reoptimization of the shortest common superstring problem
scientific article

    Statements

    Reoptimization of the shortest common superstring problem (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    20 September 2011
    0 references
    Given an instance of an optimization problem together with an optimal solution for it, the reoptimization variant tries to compute a good solution for a locally modified input instance. This paper deals with the reoptimization variants of the shortest common superstring (SCS) problem under the local modifications of adding (SCS+) or removing a single string (SCS-). The authors prove that both reoptimization versions of the SCS are NP-hard. They present two approximation algorithms for these problems. The first one is an iterative polynomial-time algorithm that achieves an approximation ratio arbitrarily close to 1.6 for SCS+ and an approximation ratio arbitrarily close to 13/7 for SCS-. These reoptimization algorithms use the existing SCS algorithms. The ratios are achieved by using the current best known approximation algorithms for SCS whose ratio is 2.5. The second one is a simple and efficient quadratic time algorithm for SCS+ that achieves an approximation ratio of 11/6, outperforming the best known ratio for SCS. The authors prove that this lower bound is tight. The proposed algorithms are simple, but the complete and thorough analyses of these algorithms are rather technical.
    0 references
    0 references
    reoptimization
    0 references
    shortest common superstring
    0 references
    approximation algorithms
    0 references

    Identifiers