algorithm - 集合被覆の欲張りアルゴリズムではありません

Question

私のセットの詳細：各セットには正確にM個の要素があり、各要素は正確にN個のセットに属しています。

最小集合被覆のサイズを計算するには、欲張りでないアルゴリズムが必要です。

良いアルゴリズムはありますか？（私の特別な場合）

ありがとう。

Answer 1

硬度の結果と、おそらく近似できない結果（おそらく定数が悪い）は、特別な場合にも当てはまります。GLPKなどの混合整数プログラムにはソルバーを使用します。