Data di Pubblicazione:
2009
Citazione:
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].
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.
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.
Tipologia CRIS:
4.1 Contributo in Atti di convegno
Elenco autori:
Bilò, Davide; BÖCKENHAUER HANS, Joachim; Komm, Dennis; Královic, Richard; Mömke, Tobias; Seibert, Sebastian; Zych, Anna
Link alla scheda completa:
Titolo del libro:
Combinatorial Pattern Matching
Pubblicato in: