Spider covers for prize-collecting network

Spider covers for prize-collecting
network activation problem
福永拓郎
国立情報学研究所
JST, ERATO, 河原林巨大グラフプロジェクト
2015 年 1 月 24 日
研究成果
スパイダー被覆アルゴリズム
ネットワーク設計のための貪欲法
• 点重みシュタイナー木問題
• 点重みシュタイナーネットワーク問題
• ネットワークアクティベーション問題
1
違反ペナルティ付きネットワークアクティベーション問題
2
点連結度ネットワークアクティベーション問題
2/21
概要
スパイダー被覆アルゴリズム
組合せ的な解析
スパイダー分解定理
density(S) ≤
OPT
φ(G)
ネットワークアクティベーション問題
違反ペナルティ付きネットワークアクティベーション問題
3/21
概要
スパイダー被覆アルゴリズム
組合せ的な解析
線形計画 (LP) による解析
スパイダー分解定理
• LP 緩和問題の定式化
density(S) ≤
OPT
φ(G)
• 主双対アルゴリズム
ネットワークアクティベーション問題
違反ペナルティ付きネットワークアクティベーション問題
3/21
組合せ最適化問題と線形計画問題 (LP)
整数最適解
4/21
組合せ最適化問題と線形計画問題 (LP)
組合せ最適化
= LP + 整数性
整数最適解
LP 最適解
4/21
組合せ最適化問題と線形計画問題 (LP)
組合せ最適化
= LP + 整数性
整数最適解
LP 最適解
• LP ∈ P, 組合せ最適化 ∈ NP 困難
• LP 最適解 ≤ 整数最適解 (最小化問題の場合)
4/21
組合せ最適化問題と線形計画問題 (LP)
α× LP 最適値
組合せ最適化
= LP + 整数性
整数最適解
LP 最適解
• LP ∈ P, 組合せ最適化 ∈ NP 困難
• LP 最適解 ≤ 整数最適解 (最小化問題の場合)
• 「整数最適解 ≤ α×LP 最適解」⇒ α 近似アルゴリズム
(整数ギャップ)
4/21
LP 緩和を用いたアプローチ
組合せ的アルゴリズム
LP を用いたアルゴリズム
• 計算速度は速いことが
多い
• 汎用 LP ソルバー
⇒ 計算速度で不利 (?)
• 問題に特化した解析
• 拡張しやすい
オーダーメイド
汎用的なフレームワーク
LP を用いたアルゴリズムの難しいところ
• LP 緩和問題の定式化は一意ではない (良い定式化 ⇒ 良い近似比)
• 整数解と LP 最適解の比をどのように抑えるか
5/21
ネットワークアクティベーション問題
• 無向グラフ G = (V , E )
• 点重み x : V → W (0 ∈ W ⊆ Z+ )
• ∀uv ∈ E : 単調アクティベーション関数
ψ uv : W × W → {true, false}
x が uv ∈ E をアクティベート
⇔ ψ uv (xu , xv ) = true
6/21
ネットワークアクティベーション問題
ネットワークアクティベーション問題
• 解
点重み x : V → Z+
• 制約
• 目的
連結度 (si , ti ) ≥ di , ∀i = 1, 2, . . .
P
v∈V x(v) → 最小化
連結度 - ネットワークの耐故障性, 安定性を表現
辺連結度
= 辺を共有しない (si , ti ) パスの最大本数
点連結度
= 辺を共有しない (si , ti ) パスの最大本数
連結度 = 1, si = sj ⇒ シュタイナー木アクティベーション問題
7/21
応用: 無線ネットワーク
シグナル弱
コスト小
シグナル強
コスト大
ネットワークアクティベーション問題 = シグナルの強さを決定
8/21
違反ペナルティ付き問題
違反ペナルティ付きネットワークアクティベーション問題
連結度 (si , ti ) ≥ di or ペナルティ πi を支払う for ∀i
目的関数: 重み + ペナルティ → 最小化
例　拠点間の通信のために
「自前で回線を引く」or「既存の回線を有料で使用する」
9/21
アルゴリズムの違反ペナルティ付き問題への拡張
ペナルティなし
連結度 (si , ti ) ≥ di ⇔ (si , ti ) カット ≥ di
ペナルティあり
• 変数 yi ∈ [0, 1]
• 目的関数= 重み +
P
i
πi yi
制約: (si , ti ) カット ≥ di · (1 − yi )
アルゴリズム
• yi < 1/2 ⇒ yi := 0 (連結度制約を満たす)
• yi ≥ 1/2 ⇒ yi := 1 (ペナルティを支払う)
ペナルティなしの整数ギャップ α ⇒ ペナティありへの 2α 倍近似
10/21
スパイダー被覆アルゴリズム (for シュタイナー木)
スパイダー
• 木
• 次数 3 以上の点は高々一つ
• 全ての葉は端点
スパイダー被覆アルゴリズム
while(# 端点 > 1)
• スパイダー S （のようなもの）と, S
をアクティベートする点重み x のペ
アで密度最小のものを求める
• S を縮約
密度 (S, x)
P
x(v)
:= v∈V
#端点 in S
それまでの重みを全て足し合わせて出力
11/21
スパイダー分解
定理 [Klein, Ravi 1993]
任意のシュタイナー木は次のようなスパイダーの集合に分解できる
• スパイダー同士は互いに点を共有しない
• 各端点はいずれかのスパイダーに含まれる
∃S, x : 密度(S, x) ≤
OPT
#端点 in G
12/21
スパイダー被覆アルゴリズムの LP による解析
既存の解析 (辺連結度制約)
∃ S, x
x(v)
OPT
≤
#端点 in S
# 極小要求カット
P
v∈V
LP に基づく解析
∃ S, x
x(v)
LP
≤
#端点 in S
# 極小要求カット
P
v∈V
整数ギャップ = O(k log n)
13/21
LP の素朴な定式化
変数
u
x(u, ω) ∈ [0, 1]: u に ω を割り当て?
y(uv, ω) ∈ [0, 1]: uv を xu = ω でアクティベート?
v
x(v, ω 0 ) ∈ [0, 1]: v に ω 0 を割り当て?
• y(uv, ω) = 1 ⇒ x(u, ω) = 1
x(u, ω) ≥ y(uv, ω)
• y(uv, ω) = 1
⇒ ψ uv (ω, ω 0 ) = true なるいずれかの ω 0 に対し x(v, ω 0 ) = 1
X
x(v, ω 0 ) ≥ y(uv, ω)
ω 0 :ψ uv (ω,ω 0 )=true
14/21
LP の素朴な定式化
min
W
XX
ω · x(v, ω)
v∈V ω=0
s.t.
W
X X
y(uv, ω) ≥ 1
要求カット X
uv∈δ(X ) ω=0
x(u, ω) ≥ y(uv, ω)
X
uv ∈ E , ω = 0, . . . , W ,
x(v, ω 0 ) ≥ y(uv, ω) uv ∈ E , ω = 0, . . . , W ,
ω 0 :ψ uv (ω,ω 0 )=true
x(v, ω), y(uv, ω) ∈ [0, 1]
15/21
素朴な定式化の整数ギャップは大きい
• 要求カット X
• 全ての辺は xu = ω でアクティベートされる
X
v1
v2
v3
v4
vm
y(uvi , ω) = 1/m
..
..
x(u, ω) = 1/m
u
LP 解
x(u, ω) = 1/m
⇒ 目的関数 =
整数解
u に ω を割り当て ⇒ 目的関数 =
ω/m
ω
16/21
素朴な定式化の整数ギャップは大きい
• 要求カット X
• 全ての辺は xu = ω でアクティベートされる
X
v1
v2
v3
v4
vm
y(uvi , ω) = 1/m
..
..
x(u, ω) = 1/m
u
なぜ?
x(u, ω) ≥ maxv y(uv, ω)
⇒ x(u, ω) 小
P
P
uv∈δ(X )
ω y(uv, ω) ≥ 1
LP 解
x(u, ω) = 1/m
⇒ 目的関数 =
整数解
u に ω を割り当て ⇒ 目的関数 =
ω/m
ω
16/21
もう一つの試み
x(u, ω) ≥ maxv y(uv, ω) → x(u, ω) ≥
P
v
y(uv, ω)?
x(u, ω) = m
y(uvi , ω) = 1
X1
X2
LP 解
x(u, ω) = m
⇒ 目的関数 =
整数解
u に ω を割り当て ⇒ 目的関数 =
Xm
mω
ω
17/21
提案 LP
試み 1
試み 2
P
x(u, ω) ≥
v y(uv, ω)
P
P
uv∈δ(X )
ω y(uv, ω) ≥ 1
x(u, ω) ≥ maxv y(uv, ω)
P
P
uv∈δ(X )
ω y(uv, ω) ≥ 1
解での高い次数が大きい整数ギャップの原因
提案 LP
変数 y(uv, ω, M) for ∀uv ∈ E , ∀ω ∈ Ω, ∀極小要求カット M
「要求カット X : M ⊆ X を被覆するために uv をアクティベート?」
X
x(u, ω) ≥ max
y(uv, ω, M)
M
uv∈E
18/21
提案 LP
min
W
XX
ω · x(v, ω)
v∈V ω=0
s.t.
W
X X
y(uv, ω, M) ≥ 1
極小要求カット M, X : M ⊆ X ,
uv∈δ(X ) ω=0
x(u, ω) ≥ max
M
x(v, ω) ≥ max
M
X
y(uv, ω, M)
u ∈ V , ω = 0, . . . , W ,
uv∈E
X
y(uv, ω 0 , M) v ∈ V , ω = 0, . . . , W ,
uv∈E ω 0
x(v, ω), y(uv, ω, M) ∈ [0, 1]
19/21
LP ≤ ネットワークアクティベーション問題
• y(·, ·, M) は {X : M ⊆ X } の極小被覆を表現
• {X : M ⊆ X } はリング族 (∩, ∪ について閉じている)
辺集合 F がリング族の極小被覆ならば，
グラフ (V , F ) を向き付けしたグラフで
最大入次数 & 最大出次数 ≤
1
定理
提案 LP ≤ OPT
20/21
まとめ
スパイダー被覆アルゴリズム
組合せ的な解析
線形計画 (LP) による解析
スパイダー分解定理
• LP 緩和問題の定式化
density(S) ≤
OPT
φ(G)
• 主双対アルゴリズム
ネットワークアクティベーション問題
違反ペナルティ付きネットワークアクティベーション問題
21/21

Download Report