Given 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 |