Reoptimization of Weighted Graph and Covering Problems

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:

We provide a PTAS for reoptimization of the unweighted versions of the aforementioned problems when the input solution is optimal.

We provide two general techniques for analyzing approximation ratio of the weighted reoptimization problems.

We apply our techniques to reoptimization of the considered optimization problems and obtain tight approximation ratios in all the cases.