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. © 2009 Springer Berlin Heidelberg.
Titolo: | Reoptimization of the Shortest Common Superstring Problem (Extended Abstract) | |
Autori: | ||
Data di pubblicazione: | 2009 | |
Serie: | ||
Handle: | http://hdl.handle.net/11697/179718 | |
ISBN: | 978-3-642-02440-5 978-3-642-02441-2 | |
Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.