欲張りアルゴリズムを使用して、集合被覆問題の解決策を実装しようとしています。
そのための古典的な欲張り近似アルゴリズムは
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つの部分で質問があります：
a。アルゴリズムを逆に実行することは有効なアルゴリズムになりますか？
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。問題の性質は、Cを取得するのが簡単で、冗長なセットの数が限られている（<5）というものです。この場合、この削除アルゴリズムのパフォーマンスは向上しますか？