Алгоритм Greedy Set Coverage, построенный на * удалении * множеств

Question

Я пытаюсь реализовать решение для заданной проблемы покрытия, используя жадный алгоритм.

Классический алгоритм жадного приближения для него

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.  

У меня вопрос в 2 частях:

а. Будет ли выполнение алгоритма в обратном порядке действительным, т.е.

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.  

б. Природа проблемы такова, что легко получить C и будет ограниченное количество (<5) избыточных наборов - в этом случае этот алгоритм удаления будет работать лучше?

Answer 1

Алгоритм обязательно вернет действительное покрытие набора, так как на каждом шаге он проверяет, являются ли все элементы s избыточными. Интуитивно я чувствую, что часть b верна, хотя я не могу написать формальное доказательство этого. Прочитайте главу 2 Виджая Вазирани, так как это может помочь в части анализа.