セットカバー - いくつかの異なるバージョン

Question

私は頂点LとRの2つのセットとエッジセットEを持つ2部グラフを使って作業しています。解決しようとしている2つの異なる問題があります：

1）単純なカバー問題（すなわち、L内の頂点の最小基数部分集合を見つけ、その部分集合の近傍にすべてのRが含まれるようにする）。私が理解するように、この問題は打撃セットの問題として知られており、セットカバーの問題といくつかの近似アルゴリズムが存在します。私はあなたがお勧めする近似アルゴリズムを知りたかったので、私はいくつかのものをオンラインで見つけました。

2）私が解決したい2番目の問題は上記と似ていますが、Rのすべてを説明するのではなく、RのサブセットであるTだけを記述したいと思います。許容される演算には、和集合と差の設定と、Lの要素の近傍の交点の設定が含まれます。したがって、そのような記述に含める必要のあるLの要素の最小数を探したいと思います。申し訳ございませんが、これが不明な場合は、さらに説明して質問に回答できます。

本当に助けていただければ幸いです。

Answer 1

1の場合は、integer linear programmingをお勧めします。そこには多くのソルバーがあります。私は個人的にGLPK（無料）とCPLEX（商業）を使用しました。

直感的には、選択されたセットによって誘導されるVennダイアグラムに、T内の要素とT内の要素の両方が含まれていないという特性を持たせたいと思います。（私は、数式中の空集合が許される。）この問題を単純な集合カバー問題に以下のように減らすことができる。カバーされる新しい要素は、TのすべてのxとR - Tの2つの要素集合{x、y}です。各古い集合Sは、新しい集合{{x, y} | x in S and y in R - S}を生成します。