セットカバー（個々のインスタンス）の貪欲アルゴリズムの近似率の上限値

Question

無意識のうちに、私は貪欲アルゴリズムの近似率の上限を見つけて（証明する）集合カバー問題の個々のインスタンスについて得られる。私がライブラリに持っている問題については、この比の限界は、問題の一般的なケースでよく知られている式を使って得られる値よりも優れています。

どういうわけか使用できますか？それとも無駄な結果ですか？

Answer 1

つまり、インスタンスごとに下限を計算できます。古典的なCS理論のアプローチは、集合カバーのLP緩和に二重である分数パッキング問題を解くことです。各集合に対して、各集合に対して、その集合の要素のコストの合計が最大でもセットのコスト。目的は要素コストの各要素の合計を最大化することです。

品質にとって計算上の経費を掛けるより強力な緩和がある（例えば、単一要素にコストを割り当て、k要素のサブセットにコストを割り当てるのではなく）。