Change search
ReferencesLink to record
Permanent link

Direct link
Reoptimization of the Shortest Common Superstring Problem
University of Sassari.
ETH Zurich.
ETH Zurich.
ETH Zurich.
Show others and affiliations
2011 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 61, no 2, 227-251 p.Article in journal (Refereed) Published
Abstract [en]

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.
Keyword [en]
reoptimization, shortest common superstring, approximation
National Category
Computer Science
URN: urn:nbn:se:kth:diva-41549DOI: 10.1007/s00453-010-9419-8ISI: 000293234800001ScopusID: 2-s2.0-80051547313OAI: diva2:444612
QC 20111003Available from: 2011-10-03 Created: 2011-09-29 Last updated: 2012-01-15Bibliographically approved

Open Access in DiVA

fulltext(238 kB)335 downloads
File information
File name FULLTEXT01.pdfFile size 238 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopusThe original publication is available at

Search in DiVA

By author/editor
Mömke, Tobias
In the same journal
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 335 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 51 hits
ReferencesLink to record
Permanent link

Direct link