k-サブモジュラーカバー問題の効率的決定論的二基準近似アルゴリズム

我々は、サイズ n の基底集合 V に対する k-サブモジュラーカバー (kSC) 問題を考察する。この問題の目標は、与えられた閾値を超える k-サブモジュラー効用関数を満たすために、最小コストで k 個の V の互いに素な部分集合を見つけることである。この問題は、よく知られているサブモジュラーカバー (SC) 問題を一般化し、人工知能や組合せ最適化において多くの応用を持つ。しかし、既存の kSC に対する近似アルゴリズムは、多項式時間で実行できない場合がある。本研究では、パフォーマンス保証を改善するだけでなく、最先端のアルゴリズムと比較してクエリ複雑性を大幅に削減する二基準近似アルゴリズムを提案する。