Reoptimization of the Maximum Weighted Pk-Free Subgraph Problem under Vertex Insertion

The reoptimization issue studied in this paper can be described as follows: given an instance I of some problem Π, an optimal solution OPT for Π in I and an instance I′ resulting from a local perturbation of I that consists of insertions or removals of a small number of data, we wish to use OPT in order to solve Π in I′, either optimally or by guaranteeing an approximation ratio better than that guaranteed by an ex nihilo computation and with running time better than that needed for such a computation. In this setting we study the weighted version of max weighted P k -free subgraph. We then show, how the technique we use allows us to handle also bin packing.ouinonouirechercheInternationa