頂点カバー問題のカーネル化アルゴリズムの最適化アルゴリズムを実装しています: 理論と実験 (PDF) 。
章 2.3: Kernelization by linear programmingで少し行き詰まっています。
この手法 (ILP の定式化) の考え方は、次の制約を満たすために、入力グラフのX_u \in \left\{ 0,1 \right\}各頂点u( としても示される) に重みを割り当てることです。vG=\left\( V,E \right\)
- 重みの合計を最小化する
\Sigma_uX_u - グラフのエッジで接続されている場合は
X_u + X_v \geq 1いつでも満足します。\left\{ u,v \right \}
したがって、出力としてX_v、1 の頂点と残りX_vの 0を持つ頂点のセットが得X_u \in \left \{ 0,1 \right \}られX_u \geq 0ます。( S. Khuller (PDF)は、この場合それを指摘していX_u \in \left \{ 0,0.5,1 \right \}ます)。その緩和により、重みが 1、0.5、および 0 の頂点の 3 つのグループができます。
私の問題は、重みの割り当てにどのようにアプローチするかがよくわからないことです。
私が理解できたことから、重みの合計を最小限に抑えるには、(エッジごとに) 最初に次数が最も高い頂点に焦点を合わせ、それらの重みが既にゼロより大きい場合は、頂点に値を追加するのが最善です解析されたエッジの 2 番目の端。
X_v \in \left \{ 0,1 \right \}これにより、(正確に?)基本的な定式化の各頂点が実際にある状況につながります。整数制約を緩和しようと考えていると、 に変わりますX_v \in \left \{ 0,0.5 \right \}。
私の論理の欠陥は何ですか？
重みが 1 と 0、および 0.5 の頂点を持つには、緩和にどのようにアプローチする必要がありますか?