Preserving approximation in the Min-Weighted Set Cover Problem

In this paper we prove that the approximate solutions to the Min-Weighted Set Cover Problem provided by Chvatal's algorithm are combinatorially k-stable with respect to element insertions. Intuitively speaking, we define an approximate solution as combinatorially k-stable with respect to an update operation if its approximation ratio remains the same 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 performed, the approximation ratio is preserved at no computational cost. In particular, we show that any solution returned by Chvatal's algorithm is combinatorially O(log m)-stable with respect to insertions, where in is the number of items in the instance. Hence, since the approximation ratio O(log m) is optimal, the best level of approximability is preserved.