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 where the local modifications consist of adding or removing a single string. We show NP-hardness of these reoptimization problems and design several approximation algorithms for them.
Reoptimization of the Shortest Common Superstring Problem / Bilò, Davide; BÖCKENHAUER HANS, Joachim; Komm, Dennis; Královic, Richard; Mömke, Tobias; Seibert, Sebastian; Zych, Anna. - 5577:(2009), pp. 78-91. ( 20th Annual Symposium on Combinatorial Pattern Matching 2009 Lille, France ) [10.1007/978-3-642-02441-2_8].
Reoptimization of the Shortest Common Superstring Problem
BILÒ, Davide;
2009-01-01
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 where the local modifications consist of adding or removing a single string. We show NP-hardness of these reoptimization problems and design several approximation algorithms for them.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
