セットカバー近似

Question

私は近似アルゴリズムについて学び始めました 私はそれについての本を読んでいますが、セットカバーアルゴリズムの分析は分かりません。

誰かがlemma 2.3を説明できますか？ それは短いですが、私はそれを理解していない...

http://view.samurajdata.se/psview.php?id=0482e9ff&page=13

Answer 1

アルゴリズムは、その価格が慣れセットSのコストで宇宙Uの各要素に「価格」price(e)を割り当てていますeを新規にセットSでカバーされる要素の数で割ったもの（既にカバーされた要素は、アルゴリズムの定義のために以前のセットよりも低い価格に割り当てられていなければならない）。

合計コストがOPTであるセットのセットを選択する最適解が存在します。その解決策はすべての要素をカバーしているため、まだカバーされていない要素はすべてカバーしています。残りの要素（証明書の表記でCBarの集合）をコストOPTでカバーすることは、コスト効率（別名価格）の定義によってコスト効率OPT/|CBar|で各要素をカバーすることを意味します。最適解が残りの要素すべてをカバーする集合を含むので、少なくとも1つの残りの要素をカバーする最適解から集合Sを選択すると仮定する（補題2.3のe_k）。最良のコスト効率を持つセットを選択しているので、そのコスト効率は、最適解のセットの平均費用対効果と少なくとも同程度でなければならないことに注意してください。OPT/|CBar|

最後の部分は、定義のために|CBar|=n-(k-1)=n-k+1としてk-1要素が既にカバーされており、私たちは要素kを対象にしています。したがって、S、したがってprice(e_k)の費用対効果は、OPT/(n-k+1)によって制限されます。