Back to Search
Start Over
Reoptimization of the Shortest Common Superstring Problem
- Source :
- Algorithmica, Algorithmica, 61 (2)
- Publication Year :
- 2011
- Publisher :
- University of Sassari, 2011.
-
Abstract
- A reoptimization problem describes the following scenario: given an instance of an optimization problem together with an optimal solution for it, we want to find a good solution for a locally modified instance. In this paper, we deal with reoptimization variants of the shortest common superstring problem (SCS) where the local modifications consist of adding or removing a single string. We show the NP-hardness of these reoptimization problems and design several approximation algorithms for them. First, we use a technique of iteratively using any SCS algorithm to design an approximation algorithm for the reoptimization variant of adding a string whose approximation ratio is arbitrarily close to 8/5 and another algorithm for deleting a string with a ratio tending to 13/7. Both algorithms significantly improve over the best currently known SCS approximation ratio of 2.5. Additionally, this iteration technique can be used to design an improved SCS approximation algorithm (without reoptimization) if the input instance contains a long string, which might be of independent interest. However, these iterative algorithms are relatively slow. Thus, we present another, faster approximation algorithm for inserting a string which is based on cutting the given optimal solution and achieves an approximation ratio of 11/6. Moreover, we give some lower bounds on the approximation ratio which can be achieved by algorithms that use such cutting strategies.<br />Algorithmica, 61 (2)<br />ISSN:0178-4617<br />ISSN:1432-0541
- Subjects :
- Optimization problem
General Computer Science
shortest common superstring
Reoptimization
Shortest Common Superstring
Approximation algorithms
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Data processing, computer science
Shortest common superstring
reoptimization
0202 electrical engineering, electronic engineering, information engineering
approximation
Mathematics
Computer Sciences
Applied Mathematics
String (computer science)
Approximation algorithm
Computer Science Applications
Datavetenskap (datalogi)
010201 computation theory & mathematics
Theory of computation
020201 artificial intelligence & image processing
ddc:004
Algorithm
Subjects
Details
- Language :
- English
- ISSN :
- 01784617 and 14320541
- Database :
- OpenAIRE
- Journal :
- Algorithmica, Algorithmica, 61 (2)
- Accession number :
- edsair.doi.dedup.....937327b5698ca0bc264c519d3697e9fa