CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishGiven an instance of an optimization problem and a good solution of that instance, the reoptimization is a concept of analyzing how does the solution change when the instance is locally modified. We investigate reoptimization of the following problems: Maximum Weighted Independent Set, Maximum Weighted Clique, Minimum Weighted Dominating Set, Minimum Weighted Set Cover and Minimum Weighted Vertex Cover. The local modifications we consider are addition or removal of a constant number of edges to the graph, or elements to the covering sets in case of Set Cover problem. We present the following results: 1 We provide a PTAS for reoptimization of the unweighted versions of the aforementioned problems when the input solution is optimal. 1 We provide two general techniques for analyzing approximation ratio of the weighted reoptimization problems. 1 We apply our techniques to reoptimization of the considered optimization problems and obtain tight approximation ratios in all the cases. © 2009 Springer Berlin Heidelberg.
| Titolo: | Reoptimization of weighted graph and covering problems | |
| Autori: | ||
| Data di pubblicazione: | 2009 | |
| Serie: | ||
| Handle: | http://hdl.handle.net/11697/179700 | |
| ISBN: | 978-3-540-93979-5 978-3-540-93980-1 | |
| Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |
File in questo prodotto:
http://hdl.handle.net/11697/179700
Copyright © 2022