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.

Gambosi, G., Protasi, M., Talamo, M. (1997). Preserving approximation in the Min-Weighted Set Cover Problem. DISCRETE APPLIED MATHEMATICS, 73(1), 13-22 [10.1016/S0166-218X(96)00047-9].

### Preserving approximation in the Min-Weighted Set Cover Problem

#### Abstract

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.
##### Scheda breve Scheda completa Scheda completa (DC)
1997
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore INF/01 - Informatica
English
Gambosi, G., Protasi, M., Talamo, M. (1997). Preserving approximation in the Min-Weighted Set Cover Problem. DISCRETE APPLIED MATHEMATICS, 73(1), 13-22 [10.1016/S0166-218X(96)00047-9].
Gambosi, G; Protasi, M; Talamo, M
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/2108/41962`
• ND
• ND
• ND