離散最適化基礎論 (11) 演習問題 2015 年 1 月 9 日岡本吉央提出締切： 2015 年 1 月 23 日ただし，x ∈ RE が変数であり，δ(v) は頂点 v に接続する辺復習問題 11.1 次の整数計画問題 (P) を考える． (P) maximize 全体の集合を表す．この問題 (P) の線形計画緩和 (LP) は c x 以下の問題である． x1 + 2x2 ≤ 2, subject to 2x1 + x2 ≤ 2, (LP) maximize subject to x1 , x2 ∈ Z. c x subject to x1 + 2x2 ≤ 2, max w≥0 2x1 + x2 ≤ 2, が x1 ≥ 0, x2 ≥ 0. 3 2 G = (V, E) と非負頂点重み関数 w : V → R が入力として与えられ，w に関する G の最小重み頂点被覆を出力する． (LP) の最適値 (P) の最適値次の問題 (P) は，最小重み頂点被覆問題を整数計画問題として定式化したものである． (P) 復習問題 11.2 次の整数計画問題 (P) を考える． minimize subject to w(v)yv ∑ yv ≥ 1 (∀ e ∈ E), yv ∈ {0, 1} (∀ v ∈ V ). v∈e Ax ≤ b, x ∈ Zn . ただし，y ∈ RV が変数である．この問題 (P) の線形計画緩ただし，変数は x であり，A ∈ Rm×n , b ∈ Rm , c ∈ Rn は定和 (LP) は以下の問題である．数である．この問題の線形計画緩和 (LP) は以下の問題である． (LP) minimize subject to ∑ v∈V c x maximize (LP) の最適値 (P) の最適値以上であるようなグラフ G が存在することを証明せよ．が何であるか，定めよ． (LP) (∀ e ∈ E). 復習問題 11.4 最小重み頂点被覆問題では，無向グラフ問題 (P) の整数性ギャップ，つまり， subject to (∀ v ∈ V ), このとき，問題 (P) の整数性ギャップ，つまり， maximize (P) maximize xe ≤ 1 0 ≤ xe ≤ 1 線形計画緩和 (LP) は以下の問題である． c≥0 ∑ e∈δ(v) ただし，x1 , x2 が変数であり，c ∈ R2 は定数である．その max xe e∈E x1 ≥ 0, x2 ≥ 0, (LP) ∑ ∑ w(v)yv v∈V c x subject to Ax ≤ b. ∑ yv ≥ 1 (∀ e ∈ E), 0 ≤ yv ≤ 1 (∀ v ∈ V ) v∈e 問題 (LP) の許容領域が整凸多面体であるとき，(P) の整数性ギャップが 1 となることを証明せよ．このとき，任意の自然数 n ≥ 2 に対して問題 (P) の整数性復習問題 11.3 最大重みマッチング問題では，無向グラフギャップ，つまり， G = (V, E) と非負辺重み関数 w : E → R が入力として与えられ，w に関する G の最大重みマッチングを出力する． max w≥0 次の問題 (P) は，最大重みマッチング問題を整数計画問が2− 題として定式化したものである． ∑ (P) maximize xe 2 n (P) の最適値 (LP) の最適値以上であるような頂点数 n のグラフ G が存在することを証明せよ． e∈E subject to ∑ xe ≤ 1 (∀ v ∈ V ), (裏に続く) e∈δ(v) xe ∈ {0, 1} (∀ e ∈ E). 1 追加問題 11.5 問題 11.3 にある問題 (P) と (LP) を考える．次の図に挙げるグラフを入力とするとき，(P) の整数性ギャップが 5 4 以上となることを証明せよ．追加問題 11.6 問題 11.3 にある問題 (P) と (LP) を考える．次の図に挙げるグラフを入力とするとき，(P) の整数性ギャップが 8 7 以上となることを証明せよ．追加問題 11.7 問題 11.4 にある問題 (P) と (LP) を考える．次の図に挙げるグラフを入力とするとき，(P) の整数性ギャップが 4 3 以上となることを証明せよ． 2