Greedy Set algorithme de couverture construit par * suppression * ensembles

Question

J'essaye de mettre en œuvre une solution pour un problème de couverture d'ensemble en utilisant un algorithme glouton.

L'algorithme d'approximation avide classique car il est

input: collection C of sets over universe U , costs: C→R ≥0  
output: set cover S 
1. Let S←∅. 
2. Repeat until S covers all elements: 
3. Add a set s to S, where s∈C maximizes the number of elements in s not yet covered by set s in S, divided by the cost c(s). 
4. Return S. 

J'ai une question en 2 parties:

a. Le fait de faire l'algorithme en sens inverse sera un algorithme valide, c'est-à-dire

input: collection C of sets over universe U , costs: C→R ≥0  
output: set cover S 
1. Let S←C . 
2. Repeat until there are no s∈S such that S-s=S (i.e. all elements in s are redundant): 
3. Remove a set s from S, where s∈S minimises the number of elements in s, divided by the cost c(s). 
4. Return S. 

b. La nature du problème est telle qu'il est facile d'obtenir C et il y aura un nombre limité (< 5) d'ensembles redondants - dans ce cas cet algorithme de retrait fonctionnerait-il mieux?

Answer 1

L'algorithme retournera sûrement une couverture de jeu valide car à chaque étape il vérifie si tous les éléments de s sont redondants. Intuitivement je sens que la partie b est vraie bien que je ne puisse pas en écrire une preuve formelle. Lisez le chapitre 2 de Vijay Vazirani car cela pourrait aider à faire la partie analyse.