Reoptimization of the Shortest Common Superstring Problem
2011 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 61, no 2, 227-251 p.Article in journal (Refereed) Published
A reoptimization problem describes the following scenario: given aninstance of an optimization problem together with an optimal solution forit, we want to find a good solution for a locally modified instance.
In this paper, we deal with reoptimization variants of the shortest commonsuperstring problem (SCS) where the local modifications consist of adding orremoving a single string. We show the NP-hardness of thesereoptimization problems and design several approximation algorithms forthem. First, we use a technique of iteratively using any SCS algorithm todesign an approximation algorithm for the reoptimization variant of addinga string whose approximation ratio is arbitrarily close to 8/5 andanother algorithm for deleting a string with a ratio tending to 13/7. Bothalgorithms significantly improve over the best currently known SCSapproximation ratio of 2.5. Additionally, this iteration technique can be usedto design an improved SCS approximation algorithm (without reoptimization)if the input instance contains a long string, which might be of independentinterest. However, these iterative algorithms are relatively slow. Thus,we present another, faster approximation algorithm for inserting a stringwhich is based on cutting the given optimal solution and achieves anapproximation ratio of 11/6. Moreover, we give some lower bounds onthe approximation ratio which can be achieved by algorithms that use suchcutting strategies.
Place, publisher, year, edition, pages
2011. Vol. 61, no 2, 227-251 p.
reoptimization, shortest common superstring, approximation
IdentifiersURN: urn:nbn:se:kth:diva-41549DOI: 10.1007/s00453-010-9419-8ISI: 000293234800001ScopusID: 2-s2.0-80051547313OAI: oai:DiVA.org:kth-41549DiVA: diva2:444612
QC 201110032011-10-032011-09-292012-01-15Bibliographically approved