整数線形プログラムのNP完全性

Question

これは宿題の問題であるので、解決策が欲しくありません。私は以下のものに縮小する問題および/またはそれを始める方法が必要です。私たちはTSPや独立したセットを考えていましたが、解決策を思いつくことができませんでした。

$ i \ ldots j $ ストアと $ i \ ldots n $ 可能な場所新しい倉庫を建設します。新しい倉庫を構築するための費用は、 $ c_j $ です。各店舗と倉庫の間には、コスト $ d_ {i、j} $ です。すべての店舗を少なくとも1つの倉庫に接続する必要があります。

決定問題は次のとおりです。合計が特定の数値 $ k $ より小さいように、一連の倉庫とパスがあります。

Answer 1

これは古典的な施設の場所問題。 Wikipediaの記事は、NP硬さがセットカバーを設定することによって証明できることを示唆しています。 >

---

Vertex Cover から縮小することで解決策が見つかったので、私は先に進み、 Set Cover ：

からの削減を明らかにします。

各値にはストアを作成します。セットごとに、倉庫を作成します。各ウェアハウスのコストを1に割り当てる1.倉庫のセットがその店舗の値を含む場合、またはそうでなければ任意の大きな値を含む場合、倉庫から店舗へのルートのコストを任意に小さい値に割り当てます。その場合、施設問題に対する最小原価ソリューションは、元の問題の最小セットカバーに対応する倉庫のセットを正確に構築します。

$ k $ 値は、最適化の問題（セット/コストを最小化する）を決定的な問題に変換するために使用されます（ $ k $ セット/コスト？） SETカバーインスタンスの $ K $ は、 $ k $ と同じです。インスタンス「任意の小さい」値を正確に0に設定することを許可されている場合は、「任意の小さい」重みを十分に小さくするだけでなく、ある程度の量で値を付ける必要があるかもしれません。あなたはただ1未満であるすべての「任意の小さい」コストを必要とし、すべての倉庫のコストの合計よりも大きくなるようにすべての「任意の大きな」コストを必要としています。

施設の問題に整数コストのみを許可されている場合は、すべてのコストを最小公倍数でスケーリングすることで同じ結果を実現できます。