On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems

It is shown that no polynomial-time approximation scheme exists for the reoptimization of the set covering problem in inserting an element into or eliminating it from any set. A similar result is obtained for the minimum graph coloring problem in inserting a vertex with at most two incidence edges and for the minimal bin packing problem in eliminating any element.