Reoptimization of the shortest common superstring problem (Q639296)

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.