計算量理論輪講　chap5-3 M1　高井唯史.

Presentation on theme: "計算量理論輪講　chap5-3 M1　高井唯史."— Presentation transcript:

1 計算量理論輪講　chap5-3 M1　高井唯史

2 Braess’s Paradox G v 1 x s t 1 x w

3 Braess’s Paradox G d(G,1,c)=2 v x(1) 1 0(1) s t 1 x(1) w
d(G,r,c):ナッシュフローにおける最大パスのコスト

4 Braess’s Paradox H v 1 x s t 1 x w

5 Braess’s Paradox H v x(1/2) 1(1/2) s t 1(1/2) x(1/2) w d(H,1,c)=3/2

6 問題(5.1) (G,r,c)が与えられた時に、 d(H,r,c)を最小にするGの部分グラフHを求めよ。
5.3節では上記の問題を解く近似アルゴリズムについて考える。

7 5.2節の結果(1) LINEAR NETWORK DESIGN (コスト関数が線形関数) GENERAL NETWORK DESIGN
(コスト関数が任意の関数) PLYNOMIAL(p) NETWORK DESIGN (コスト関数が次数p以下の多項式) INCLINE(γ) NETWORK DESIGN (コスト関数のINCLINEがγ以下) n:頂点数 INCLINE:以下の式で定義される。直観的には関数の凸度。 大きいほどPriceOfAnarchyが悪くなる。

8 5.2節の結果(2) ネットワークの種類 以下を満たす(G,r,c)が存在する LINEAR NETWORK DESIGN
(コスト関数が線形関数) GENERAL NETWORK DESIGN (コスト関数が任意の関数) PLYNOMIAL(p) NETWORK DESIGN (コスト関数が次数p以下の多項式) INCLINE(γ) NETWORK DESIGN (コスト関数のINCLINEがγ以下) n:頂点数

9 trivialの近似度 trivialな近似アルゴリズムをH=Gとするものと定義する。 5.2節の結果より明らかに以下が成り立つ
ネットワークの種類 trivialの近似度 系5.3.1 LINEAR NETWORK DESIGN (コスト関数が線形関数) 系5.3.2 GENERAL NETWORK DESIGN (コスト関数が任意の関数) 系5.3.3 PLYNOMIAL(p) NETWORK DESIGN (コスト関数が次数p以下の多項式) 系5.3.4 INCLINE(γ) NETWORK DESIGN (コスト関数のINCLINEがγ以下) P≠NPを仮定すると、tirivialよりいい性能の近似アルゴリズムは 存在しないことがわかる。以後、これを証明する。

10 5.3.1 Linear Cost Function 定理5.3.5
P≠NPを仮定すると、LINEAR NETWORK DESIGNにおいて、任意のε>0に対して近似度を　　　　達成する近似アルゴリズムは存在しない

11 証明:定理5.3.5 既存のNP完全問題2DDPを還元する。 近似アルゴリズムが存在すると、2DDPが解けてしまう事を示す 2DDP
入力：有向グラフG=(V,E)、　　　　　　　 問題：同一頂点を含まない、パス　　　　　　とパス　　　　　が存在するか

12 証明：定理5.3.5 2DDP

13 証明：定理5.3.5 2DDP disjointな2パスが得られたのでtrue

14 証明：定理5.3.5 2DDPを還元する ?

15 ? 証明：定理5.3.5 2DDPを還元する r=1とし、多項式時間でインスタンス(G,r,c)を作成できた。 x 1 s t x 1
x 1 ? s t x 1 コスト関数すべて0 r=1とし、多項式時間でインスタンス(G,r,c)を作成できた。

16 証明：定理5.3.5 正しい2DDPのインスタンスならd(G,r,c)=2 以下を証明すればよい (1)2DDPのyesインスタンスなら
d(H,r,c)=3/2となるHが存在する (2)2DDPのnoインスタンスなら 全てのHでd(H,r,c)≧2

17 証明：(1) 2DDPのyesインスタンスのため、disjointなパス が存在する パス に含まれない枝を全て削除する
パス　　　　に含まれない枝を全て削除する sからtへdisjointなパスが二つのみ残る そのときのd(H,r,c)=3/2

18 証明(1):例 1 x s t x 1

19 証明(1):例 1 x s t x 1

20 証明(1):例 1 x s t x 1

21 証明(1):例 1/2 1(1/2) x(1/2) s t x(1/2) 1(1/2) 1/2 d(H,r,c)=3/2

22 証明(2) disjointな2つのパスが存在しない 1 x s t x 1

23 証明(2) どのように枝を切り取っても共通の頂点vが存在する 1 x s v t x 1

24 証明(2) どのように枝を切り取っても共通の頂点vが存在する 典型的なBraess’s Paradoxを引き起こす d(H,r,c)≧2 1
t x(1) 1 典型的なBraess’s Paradoxを引き起こす d(H,r,c)≧2 インスタンスな特別な場合はそれぞれで場合分けして計算する。証明終わり

25 系5.3.6 線形コスト関数であり、paradox-riddenもしくはparadox-freeな(G,r,c)が与えられた時、それがparadox-riddenかそうでないかを判定する問題はNP困難である paradox-ridden：d(G,r,c)=4d(H,r,c)/3となるHが存在する paradox-free：すべてのHにおいてd(G,r,c)≦d(H,r,c)

26 5.3.2 Arbitrary Cost Function
定理5.3.7 P≠NPを仮定すると、GENERAL　NETWORK DESIGNにおいて、任意のε>0に対して近似度を　　　　達成する近似アルゴリズムは存在しない

27 証明:定理5.3.7 既存のNP完全問題PARTITIONを還元する。
入力：q個の自然数　　　 問題：　　　　　　　　　を満たす　　　　　　　　　　は存在するか? (ここでは全て3の倍数とする)

28 証明：定理5.3.7 Braess graph 　　(k=4) s t この形を作りたい

29 証明：定理5.3.7 タイプA(並行なq本の枝 ) s t タイプB タイプC

30 証明：定理5.3.7 コスト関数を定義する タイプA 疑似枝容量 疑似枝容量１ タイプB タイプc 疑似枝容量

31 証明：定理5.3.7 (G,r,c)還元完了 並行なq本の枝 タイプA 枝容量： 1 2 タイプB 枝容量１ 4 s t 3 3

32 (G,r,c)のナッシュフロー d(G,r,c)=k+1=n/2 並行なq本の枝 タイプA 枝容量： 1 2 タイプB 枝容量１ 4 s t
3 3 タイプC　枝容量 2 4 1 d(G,r,c)=k+1=n/2

33 証明：定理5.3.7 正しいPARTITIONのインスタンスならd(G,r,c)=n/2 以下を証明すればよい
(1)PARTITIONのyesインスタンスなら d(H,r,c)=1となるHが存在する (2)PARTITIONのnoインスタンスなら 全てのHでd(H,r,c)≧n/2

34 証明:(1) 並行なq本の枝 タイプA 枝容量： 1 2 タイプB 枝容量１ 4 s t 3 3 タイプC 枝容量 2 4
全てのiでタイプAの枝容量は合計 1 この枝容量を丁度半分にするように タイプAの枝を切り取る

35 証明:(1) 並行なq本の枝 タイプA 枝容量： 1 2 タイプB 枝容量１ 4 s t 3 3 タイプC 枝容量 2 4
全てのiでタイプAの枝容量は合計 1

36 (1)のHのナッシュフロー d(H,r,c)=1 並行なq本の枝 タイプA 枝容量： 1 1 1 2 タイプB 枝容量１ 4 1 s t 3

37 証明：（２） 全てのHでd(H,r,c)≧n/2となる事を示す Hを3つの特徴にわけて示す。 性質1を持つ場合はd(H,r,c)≧M≧n/2

38 性質１：いずれかのタイプcの枝がない 並行なq本の枝 タイプA 枝容量： 1 2 タイプB 枝容量１ 4 s t 3 3 タイプC 枝容量
流すべきフロー量rを下回る d(H,r,c)≧M≧n/2

39 性質2：いずれかのiで 1 から出る最大フロー量は 2 4 s t sから出る最大フロー量は 3 3 2 4 1 流すべきフロー量rを下回る
d(H,r,c)≧M≧n/2

40 性質1,2がない場合 d(H,r,c)=k+1=n/2 このナッシュフローが存在してしまう 並行なq本の枝 タイプA 枝容量： 1 2
タイプB　枝容量１ 4 s t 3 3 タイプC　枝容量 2 4 1 このナッシュフローが存在してしまう d(H,r,c)=k+1=n/2 証明終わり

41 系5.3.8 任意のコスト関数において、paradox-riddenもしくはparadox-freeな(G,r,c)が与えられた時、それがparadox-riddenかそうでないかを判定する問題はNP困難である paradox-ridden：d(G,r,c)= d(H,r,c)となるHが存在する paradox-free：すべてのHにおいてd(G,r,c)≦d(H,r,c)

42 5.3.3 Other Sets of Cost Functions
定理5.3.10 P≠NPを仮定すると、POLYNOMIAL(p)　NETWORK DESIGNにおいて、近似度　を達成する近似アルゴリズムは存在しない

43 証明：5.3.10 PARTITIONから還元して証明することは、次数が低い時枝容量の議論が通用しない
コスト関数へよりもネットワークへと対応 2DDPインスタンスを　　　　個並べたBraess graphへと還元する

44 証明：5.3.10 証明の詳細は省く t s 個 yesインスタントならd(H,r,c)=小さい定数となるHが存在
noインスタントなら全てのHで　　　　　　　　　　　となるようにコスト関数を設定する　 証明の詳細は省く

45 系5.3.11 系5.3.11 P≠NPを仮定すると、GENERAL　NETWORK DESIGNにおいて、任意のε>0に対して近似度を　　　　達成する近似アルゴリズムは存在しない

46 証明：5.3.11 証明の詳細は省く t s 個 yesインスタントならd(H,r,c)=小さい定数となるHが存在
noインスタントなら全てのHで　　　　　　　　　　　となるようにコスト関数を設定する　 より 近似アルゴリズムは2DDPを解ける 証明の詳細は省く

47 定理5.3.13 定理5.3.13 P≠NPを仮定すると、INCLINE(γ)　NETWORK DESIGNにおいて、近似度　を達成する近似アルゴリズムは存在しない 証明：5.3.13 定理5.3.10と同様に証明する。略

48 5.3.4 Generalizing Edge Removals with Taxes
新しい問題を定義する コスト関数　　と非負の実数　　を用いて、 新しいコスト関数　　　　　　　　　　　を定義する。 (G,r,c)が与えられた時に、 d(G,r,c+γ)を最小にするγを求めよ。 問題(5.10) γをtaxと呼ぶ 問題(5.1)はtaxが0と∞の二つしかない特別なバージョンである

49 (5.10)のtrivialの近似度 trivialな近似アルゴリズムをγ=0とするものと定義する。
5.2節の結果より明らかに以下が成り立つ ネットワークの種類 trivialの近似度 系5.3.14 LINEAR NETWORK DESIGN (コスト関数が線形関数) 系5.3.15 GENERAL NETWORK DESIGN (コスト関数が任意の関数) 系5.3.16 PLYNOMIAL(p) NETWORK DESIGN (コスト関数が次数p以下の多項式) 系5.3.17 INCLINE(γ) NETWORK DESIGN (コスト関数のINCLINEがγ以下)

50 問題(5.10)の近似困難 ネットワークの種類 近似困難 定理5.3.18 LINEAR NETWORK DESIGN
(コスト関数が線形関数) 定理5.3.19 GENERAL NETWORK DESIGN (コスト関数が任意の関数) 定理5.3.20 PLYNOMIAL(p) NETWORK DESIGN (コスト関数が次数p以下の多項式) 定理5.3.21 INCLINE(γ) NETWORK DESIGN (コスト関数のINCLINEがγ以下)

51 定理5.3.19 近似困難性の下界が弱くなっている PARTITIONでなく2DDPを還元したから
PARTITIONのnoインスタンスの還元において、d(G,r,c+γ)=1となるγが存在するから

52 定理5.3.22 Gの全ての部分グラフHにおいて であるが、 あるγにおいて 　　となる 頂点数nの(G,r,c)が存在する

53 定理5.3.23 (G,r,c)がLINEAR NETWORL DESIGNの場合、任意のtax γについて
d(H,r,c)≦d(G,r,c+γ) を満たすHが存在する 証明略

54 コスト関数の線形と非線形 この本の他の全ての解析において 線形コスト関数と非線形コスト関数の差は、 質的な差ではなく、量的な差であった。
定理5.3.22と定理5.3.23はコスト関数が線形や非線形である事はtaxと枝の切り取りの相対的な能力に影響を与えることを意味する

55 証明：定理5.3.18 基本は問題(5.1)と同様 2DDPを同様に還元して証明する。
yesインスタンスを還元したときは定理5.3.5と同じように枝を削除するようにγを割り振ればよい noインスタンスを還元したときについて考える。