PRESERVING APPROXIMATION IN THE MIN-WEIGHTED SET COVER PROBLEM

In this paper we prove that the approximate solutions to the Min-Weigh ted Set Cover Problem provided by Chvatal's algorithm are combinatoria lly k-stable with respect to element insertions. Intuitively speaking, we define an approximate solution as combinatorially k-stable with re spect to an update operation if its approximation ratio remains the sa me even if the problem instance is modified by any sequence of at most k such operations. This implies that, if no more than k updates an pe rformed, the approximation ratio is preserved at no computational cost . In particular, we show that any solution returned by Chvatal's algor ithm is combinatorially O(log m)-stable with respect to insertions, wh ere in is the number of items in the instance. Hence, since the approx imation ratio O(log m) is optimal, the best level of approximability i s preserved.