離散最適化基礎論 (12) 演習問題 2015 年 1 月 23 日岡本吉央提出締切： 2015 年 2 月 6 日復習問題 12.1 最小重み頂点被覆問題では，無向グラフ追加問題 12.3 次の整数計画問題 (P) を考える． G = (V, E) と非負頂点重み関数 w : V → R が入力として (P) 与えられ，w に関する G の最小重み頂点被覆を出力する． minimize subject to 次の問題 (P) は，最小重み頂点被覆問題を整数計画問題 minimize ∑ ただし，A ∈ Rm×n , b ∈ Rm , c ∈ Rn は定数であり，x ∈ Rn w(v)yv v∈V subject to ∑ Ax ≥ b, x ∈ {0, 1}n . として定式化したものである． (P) c> x が変数である．この問題 (P) の線形計画緩和 (LP) は以下 yv ≥ 1 (∀ e ∈ E), yv ∈ {0, 1} (∀ v ∈ V ). の問題である． v∈e (LP) minimize subject to ただし，y ∈ RV が変数である．この問題 (P) の線形計画緩 ∑ いま，A のすべての成分は非負であり，かつ，(LP) の許 w(v)yv 容領域である凸多面体において，その任意の頂点の座標が v∈V subject to ∑ Ax ≥ b, 0 ≤ x ≤ 1. 和 (LP) は以下の問題である． (LP) minimize c> x yv ≥ 1 (∀ e ∈ E), 0 ≤ yv ≤ 1 (∀ v ∈ V ). {0, 1/2, 1} の要素であると仮定する．以下の問いに答えよ． v∈e 1. 問題 (P) の整数性ギャップ，すなわち，以下の問いに答えよ． max c≥0 1. 問題 (LP) の任意の最適解の y ∗ ∈ RV とする．このとき，次のようにしてベクトル y 0 ∈ RV を構成する．すなわち，任意の v ∈ V に対して  0 (y ∗ < 1/2 のとき) v yv0 = 1 (y ∗ ≥ 1/2 のとき) (P) の最適値 (LP) の最適値が 2 以下であることを証明せよ．(ヒント：問題 12.1 を参考にして，(LP) の最適解から (P) の許容解を構成してみよ．(LP) の最適解として，その許容領域の頂点であるものが存在することを利用してもよい．(そのような最適解も多項式時間で発見できる．)) v 2. 線形計画問題が多項式時間で解けることを利用し，上とするのである．このようにして構成された y 0 が (P) の仮定を満たす問題 (P) に対して，多項式時間 2 近の許容解であることを証明せよ．似アルゴリズムを設計せよ．なぜ近似比が 2 以下であ 2. 上の小問における y ∗ と y 0 に対して， ∑ v∈V w(v)yv0 ≤ 2 ∑ るのかも説明せよ． w(v)yv∗ v∈V という不等式が成り立つことを証明せよ． 3. 以上を踏まえて，(P) の整数性ギャップが 2 以下であることを証明せよ．復習問題 12.2 線形計画問題が多項式時間で解けることを利用し，最小重み頂点被覆問題に対して，近似比が 2 以下である多項式時間アルゴリズムを設計せよ．なぜ近似比が 2 以下であるのかも説明せよ．(問題 12.1 で証明したことを用いてもよい．) 1