ネットワーク設計における貪欲法
1. 頂点重みシュタイナー木福永 拓郎
fukunaga@ise.chuo-u.ac.jp

組合せ最適化セミナー 2022 年 7 月 26 日

今回のテーマ
NP 困難問題に対する貪欲アルゴリズム

集合被覆問題 Ü グラフ上の問題
1. 頂点重みシュタイナー木
スパイダーを使った貪欲アルゴリズム
2. Uncorssable 集合族被覆スパイダーの拡張，LP を用いた解析
3. Buy-at-bulk ネットワーク設計問題
ジャンクション木を使った貪欲アルゴリズム
2/29

集合被覆問題

集合被覆問題
集合被覆問題入力• 有限集合 I (|I| = n とする)
• I の部分集合 S1 , S2 , . . . , Sm ⊆ I• 非負重み w(j) ≥ 0 (∀j ∈ M := {1, 2, . . . , m})
N ⊆ M が集合被覆 ⇔Sj∈N Sj = I

重み最小の集合被覆 N を求めよi ∈ I が Sj に含まれるとき，集合 Sj は要素 i を被覆するという．
4/29

問題例

灰色の点が I の要素，青い線が S1 , . . . , Sm を表す．

問題例

灰色の点が I の要素，青い線が S1 , . . . , Sm を表す．

5/29

集合被覆の困難性
特殊ケースとして多くの問題を含んでいる• 頂点被覆問題◦ 被覆すべきもの = 辺◦ 選ぶもの = 頂点
• 全域木問題◦ 被覆すべきもの = グラフのカット◦ 選ぶもの = 辺定理 (Feige 1998)

NP⊆ ZTIME(nO(log log n) ) でない限り，集合被覆問題ではΩ(log n) 近似より良い近似比を多項式時間では達成できない．
6/29

集合被覆問題に対する近似アルゴリズム
密度 density(j) :=w(j)Sj を選ぶと新たに被覆される要素の数が最小の集合 Sj を選び続ける．
アルゴリズム

1. i := 1, Ni−1 := ∅2. while Ni−1 が集合被覆でない:• ji := arg min density(j)• Ni := Ni−1 ∪ {ji }, i := i + 1
3. Ni−1 を出力
近似比は Hn = 1 + 1/2 + · · · + 1/n7/29

集合被覆問題の一般化

ポテンシャル関数 φ : 2M → Z≥0• 単調: φ(N ) ≤ φ(N 0 ) (∀N ⊆ N 0 )• 劣モジュラ:φ(N ∪ {i}) − φ(N ) ≥ φ(N 0 ∪ {i}) − φ(N 0 )(∀N ⊆ N 0 ⊆ M \ {i})• 今回は簡単のため φ(∅) = 0, φ(M ) = n とする．

8/29

集合被覆問題の一般化
劣モジュラ被覆問題
入力• 有限集合 M• 非負重み w(j) ≥ 0 (∀j ∈ M )• ポテンシャル関数 φ : 2M → Z≥0制約

N ⊆ M が劣モ被覆 ⇔ φ(N ) = n
重み最小の劣モ被覆 N を求めよ
集合被覆問題 Ü φ(N ) :=Si∈N Si9/29

貪欲アルゴリズム（劣モジュラ被覆）
密度 density(j) :=w(j)j を選んだ際のポテンシャルの増分劣モジュラ被覆アルゴリズム

1. i := 1, φ0 := 0
2. while φi < n:• ji := arg min density(j)• φi := φ({j1 , . . . , ji }), i := i + 1
3. {j1 , . . . , ji } を出力近似比 Hn10/29近似比の解析w(ji )OPT≤
φi − φi−1n − φi−1OPT0n近似比の解析w(ji )OPT≤φi − φi−1n − φi−1OPTw(j1 )0φ1n近似比の解析w(ji )
OPT≤
φi − φi−1n − φi−1OPTw(j1 ) + w(j2 )w(j1 )
0φ1φ2n近似比の解析w(ji )
OPT≤
φi − φi−1n − φi−1OPTw(j1 ) + w(j2 ) + w(j3 )w(j1 ) + w(j2 )w(j1 )
0

φ1

φ2

φ3n

近似比の解析w(ji )
OPT≤
φi − φi−1n − φi−1w(j1 ) + w(j2 ) + w(j3 ) + w(j4 )OPTw(j1 ) + w(j2 ) + w(j3 )w(j1 ) + w(j2 )w(j1 )
0

φ1φ2φ3n11/29

近似比w(出力解)= w(j1 ) + w(j2 ) + w(j3 ) + · · ·

φ1 − 0 φ2 − φ1 φ3 − φ2+++ ···n−0n − φ1n − φ2111
1++ ··· +++ ···n n−1n − φ1 n − φ1 − 1≤

≤



· OPT


· OPT

= Hn · OPT

12/29

主定理
w(ji )
OPT≤
φi − φi−1n − φi−1
最適解 = {1, 2, . . . , k}, Si−1 = {j1 , . . . , ji−1 } とする

OPTw(1) + w(2) + · · · + w(k)=n − φi−1φ(Si−1 ∪ {1, . . . , k}) − φ(Si−1 )w(1) + w(2) + · · · + w(k)≥ Pk
j=1 (φ(Si−1 ∪ {j}) − φ(Si−1 ))≥ minw(j)j=1,...,k φ(Si−1 ∪ {j}) − φ(Si−1 )≥w(ji )
φi − φi−1∵ 最適解の定義∵ φが劣モ∵ 演習問題∵ ji の定義
13/29

頂点重みシュタイナー木

問題設定
頂点重みシュタイナー木問題
入力• 無向グラフ G = (V, E)• 端点集合 T ⊆ V (k := |T | とする)
• 頂点重み w(v) ≥ 0 (v ∈ V )制約
シュタイナー木: T を連結にする G の部分グラフ F
出力Pv∈VF w(v) を最小化するシュタイナー木 F を求めよ

15/29

問題例

シュタイナー点端点∀v ∈ V \ T : w(v) = 1 Ü 頂点重み = 3

16/29

頂点重みシュタイナー木の近似困難性
定理
頂点重みシュタイナー木問題に対する α 近似アルゴリズム⇒ 集合被覆問題に対する α 近似アルゴリズム

S1SmI

頂点重みシュタイナー木の近似困難性定理
頂点重みシュタイナー木問題に対する α 近似アルゴリズム⇒ 集合被覆問題に対する α 近似アルゴリズム

S1SmI

頂点重みシュタイナー木の近似困難性
定理
頂点重みシュタイナー木問題に対する α 近似アルゴリズム⇒ 集合被覆問題に対する α 近似アルゴリズム

S1

SmI

17/29

頂点重みシュタイナー木の近似困難性
定理
頂点重みシュタイナー木問題に対する α 近似アルゴリズム⇒ 集合被覆問題に対する α 近似アルゴリズム

S1SmI
頂点重みは複数の辺で共有できるので難しい
17/29

頂点重みシュタイナー木問題をどうやって解く？
ナイーブなアイデア: 集合被覆問題に帰着C

頂点重みシュタイナー木問題=「Find 重み最小 V 0 ⊆ V s.t. V 0 ∩ C 6= ∅ for ∀ 頂点カット C 」
つまり，• I := {グラフの頂点カット}• Si := グラフの頂点

18/29

貪欲アルゴリズムを単純に適用すると
貪欲アルゴリズム• ポテンシャル φ := 被覆した頂点カットの数• density(v) :=w(v)/(v を選択したときのポテンシャルの増分)
効率性最小の頂点 v を選ぶことを繰り返す
問題点• どうやって効率性最小の頂点を選ぶか？
• 近似比 Hφ(V ) = Ω(n) (頂点カットの数は 2n ぐらい)

19/29

頂点重みシュタイナー木問題の解法

Klein & Ravi (1995) のアイデア
貪欲アルゴリズムを上手く適用する• 単純に集合被覆には帰着しない• 貪欲アルゴリズムの考え方をほぼそのまま利用する◦ ポテンシャル Ü k− 端点の数
◦ 集合 Ü スパイダー

20/29

スパイダーとは？
• 根から葉へのパスの結合．
• 葉は全て端点．（葉以外の頂根点は端点でもシュタイナー点でもどちらでもよい）• 葉の数 ≥ 2．
• 端点同士を結ぶ 1 本の辺も葉葉の数 = 2 のスパイダーと見なす（その場合はどちらかの端点を根とする）．

21/29

スパイダーと弱スパイダー（強）スパイダー S

弱スパイダー S 0• 葉へのパスは，根以外は• パスが頂点・辺を共有して点素• w(S) :=もいいPv∈VS w(v)• w(S 0 ) := 根以外は重みを重複してカウント
22/29

スパイダー被覆アルゴリズム• φ(G) := k− 端点の数
• 弱スパイダー S を選び縮約. 縮約でできた頂点は端点とする．

Ü φ(G) は (S に含まれる端点数 −1) 増加

w(S)/(S の葉の数)density(S) :=w(S)/(S の葉の数 + 1)

根が端点でない根が端点

密度の定義の分母をスパイダー S のポテンシャルと呼ぶ．

S のポテンシャル 6= S を縮尺したときの φ(G) の増分
23/29

スパイダー被覆アルゴリズム

スパイダー被覆アルゴリズム

1. while φ(G) < k − 1 (i.e. 端点の数 > 1)
• 密度最小の弱スパイダー S を計算• VS を縮約し，新しい頂点を端点とする
2. 計算された弱スパイダーに含まれる頂点と辺をすべて選択したものを解として出力

24/29

弱スパイダーをいかに見つけるか
密度の値は弱スパイダー S の重みと葉の数，根が端点かどうかにのみ依存．
密度最小の弱スパイダーの計算

1. For ∀v ∈ V
1.1 v から各端点への（頂点重み）最短路を計算.
1.2 For ∀k = 1, 2, . . . , |T |
最短路を重みが小さい方から k 個を選び結合することで弱スパイダーを定義. ただし，v が端点でないなら k ≥ 2のみ考える．
2. ステップ 1.2 で計算した弱スパイダーのうち，密度最小のものを出力.
25/29

近似比の解析グラフ G における密度最小の弱スパイダー S は以下を満たす．

w(S)
2OPT
≤
φ(G/S) − φ(G)k − 1 − φ(G)上の定理を認めれば，O(Hk−1 ) = O(log k) 近似．

26/29

スパイダー分解
スパイダー分解定理 [Klein, Ravi 1995]
任意のシュタイナー木は，次を満たすスパイダーの集合に分解できる.

• スパイダー同士は点素．
• 各端点はどれかのスパイダーの根もしくは葉．

27/29

スパイダー分解
スパイダー分解定理 [Klein, Ravi 1995]
任意のシュタイナー木は，次を満たすスパイダーの集合に分解できる.

• スパイダー同士は点素．
• 各端点はどれかのスパイダーの根もしくは葉．

27/29

主定理の証明
S 0 を，最適解を分解して得られるスパイダーのうち，密度最小のものとする．
w(S)
w(S)
≤
∵ 葉はすべて端点
φ(G/S) − φ(G)S のポテンシャル − 12w(S)≤S のポテンシャル
2w(S 0 )≤ 0∵ S は密度最小
S のポテンシャルP
2 S 00 ∈スパイダー分解 w(S 00 )≤P
∵ S 0 の定義
00 のポテンシャル
S
S 00 ∈スパイダー分解
2OPT≤
k − 1 − φ(G)
28/29

参考文献

1. U. Feige. A threshold of ln n for approximating set cover.
Journal of the ACM 45, 634–652, 1998.
2. P.N. Klein, R. Ravi. A nearly best-Possible approximation
algorithm for node-weighted Steiner trees. Journal ofAlgorithms 19(1), 104–115, 1995.
3. T. Fukunaga. Spider covering algorithms for network designproblems. Combinatorial Optimization and Graph Algorithms:
Communications of NII Shonan Meetings, 43–66, 2017.

29/29