caa a22 4500 445805544 CHVBK 20180608132847.0 cr unu---uuuuu 170323e20111001xx s 000 0 eng 10.1007/s00453-010-9419-8 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9419-8 Reoptimization of the Shortest Common Superstring Problem [Elektronische Daten] [Davide Bilò, Hans-Joachim Böckenhauer, Dennis Komm, Richard Královič, Tobias Mömke, Sebastian Seibert, Anna Zych] 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. Springer Science+Business Media, LLC, 2010 Reoptimization nationallicence Shortest Common Superstring nationallicence Approximation algorithms nationallicence Bilò Davide Department of Computer Science, University of L'Aquila, L'Aquila, Italy aut Böckenhauer Hans-Joachim Department of Computer Science, ETH Zurich, Zurich, Switzerland aut Komm Dennis Department of Computer Science, ETH Zurich, Zurich, Switzerland aut Královič Richard Department of Computer Science, ETH Zurich, Zurich, Switzerland aut Mömke Tobias Department of Computer Science, ETH Zurich, Zurich, Switzerland aut Seibert Sebastian Department of Computer Science, RWTH Aachen University, Aachen, Germany aut Zych Anna Department of Computer Science, ETH Zurich, Zurich, Switzerland aut Algorithmica Springer-Verlag 61/2(2011-10-01), 227-251 0178-4617 61:2<227 2011 61 453 https://doi.org/10.1007/s00453-010-9419-8 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9419-8 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Bilò Davide Department of Computer Science, University of L'Aquila, L'Aquila, Italy aut NATIONALLICENCE 700 1- Böckenhauer Hans-Joachim Department of Computer Science, ETH Zurich, Zurich, Switzerland aut NATIONALLICENCE 700 1- Komm Dennis Department of Computer Science, ETH Zurich, Zurich, Switzerland aut NATIONALLICENCE 700 1- Královič Richard Department of Computer Science, ETH Zurich, Zurich, Switzerland aut NATIONALLICENCE 700 1- Mömke Tobias Department of Computer Science, ETH Zurich, Zurich, Switzerland aut NATIONALLICENCE 700 1- Seibert Sebastian Department of Computer Science, RWTH Aachen University, Aachen, Germany aut NATIONALLICENCE 700 1- Zych Anna Department of Computer Science, ETH Zurich, Zurich, Switzerland aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/2(2011-10-01), 227-251 0178-4617 61:2<227 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence SWISSBIB 445805544 BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer