Reoptimization of the shortest common superstring problem (Q639296): Difference between revisions
From MaRDI portal
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
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
reoptimization
0 references
shortest common superstring
0 references
approximation algorithms
0 references