集合被覆問題は, 資源選択問題をモデル化した組合せ最適化問題である. この問題は NP 困難で, 効率良く最適解を求めることはできない. それゆえ, 発見的手法によるアルゴリズムと, 近似アルゴリズムが数多く提案された. 発見的アルゴリズムの性能は, 計算機実験により示されている. 一方, 近似アルゴリズムの性能は, 理論的な解析により示されている.
本研究では, これまでに提案された近似アルゴリズムを 6 種類計算機上に実装し, さまざまな問題例について実験を行なった. そしてこれらの近似アルゴリズムの性能が, 理論的に保証される性能を大きく上回ることを確認した. また, 単純な局所探索法を加えたグリーディアルゴリズムが, 他の複雑な近似アルゴリズムよりも良い性能を示すことが分かった.