需要点、供給点、辺容量を持つ

Partitioning Trees with Supply,
Demand and Edge-Capacity
（需要点、供給点、辺容量を持つ
木を分割するアルゴリズム）
西関研究室 M1309 川端真生
1
研究背景
• 電力配送問題
[伊藤 et al. ‘05]
– 各供給点はどの需要点にどれだけの電力を送れ
ばよいのか
– 各送電線には流せる電力量に上限（辺容量）が
ある [本研究]
2
分割問題
需要点
発電所
送電線
3
分割問題
需要点
8
供給点
15
25
7
辺容量
必要な電力
3
12
2
6
11
10
7
供給可能な
量
Yes, No 判定問題
2
3
20
8
7
7
7
1
15
15
辺容量
5
7
20
8
8
4
12
18
15
6
11
8
辺を除去し, いくつかの連結成分に分割
供給点
需要点
4
分割問題
１３
15
8
8
7
１５
供給点
需要点
7
3
3
12
2
6
5
20
Yes, No 判定問題
8
6
5
2 10
11 3
77
1 7
2
3
7
1
15 7
15
辺容量
25
１８
7
8
20
8
8
4
4
12
18
14
15
6
8
11
8
１８
各成分にちょうど1つの供給点
フロー
その供給量は需要量の合計以上
流れるフローは辺容量を超えない（フロー≦辺容量）5
分割問題
結果
• （辺容量のない）一般のグラフ対してＮＰ完全
[伊藤 et al. ‘05]
• （辺容量のある）木に対して
線形時間アルゴリズムを与えた
6
分割問題アルゴリズム
需要点
• 入力：
– 木（需要点,供給点,辺容量）
17
• 出力：
6
– 分割がある
– 分割がない
28
25
• 時間計算量：
辺容量
5
10
5
15
7
8
4
供給点
– 線形時間
n:点数
7
分割問題アルゴリズム
9
14
26
4
19
7
4
1
5
3
26
32
32
12
14
7
5
45
14
7
9
4
3
1
2
8
5
8
分割問題アルゴリズム
7+1+3
7
5
4
1
3
9
12
14
14
需要量≦辺容量
19
7
4
1
11
5
3
12
26
14
4
26
32
32
12
14
7
5
45
14
7
9
4
3
1
2
8
5
9
分割問題アルゴリズム
11
11
12
9 12
14
14
12
min{14,12}
4
19
32
26
32
11
12
14
7
5
26
45
14
7
9
4
3
1
2
8
5
10
分割問題アルゴリズム
11
1
12
9
14 12－11
12
26
4
19
26
32
32
11
12
12
7
5
45
14
7
9
4
3
1
2
8
5
11
分割問題アルゴリズム
9
14
26
4
19
1
26
32
32
7
5
45
14
7
9
4
3
1
2
8
5
12
分割問題アルゴリズム
9
14
26
4
19
1
26
32
27
45
14
7
9
4
3
1
2
8
5
13
分割問題アルゴリズム
9
14
26
4
19
1
32
27
26
45
14
10
9
8
5
14
分割問題アルゴリズム
9
14
26
4
19
1
32
27
26
45
14
10
14
15
分割問題アルゴリズム
9
14
26
23
26
45
14
10
14
16
分割問題アルゴリズム
9
14
23
26
2
17
分割問題アルゴリズム
5
18
分割問題アルゴリズム
9
14
26
4
19
7
4
1
5
3
26
32
32
12
14
7
5
45
14
7
9
4
3
1
2
8
5
分割あり
19
分割問題アルゴリズム
9
14
26
4
7
19
12
18
10
1
4
8
3
7
25
27
14
7
4
6
3
8
3
1
4
20
分割問題アルゴリズム
9
14
4
19
8
26
7
12
18
10
6
21
分割問題アルゴリズム
9
14
8
26
7
22
分割問題アルゴリズム
16
分割はない
時間
n:点数
23
最大分割問題
7
6
8
9
8
6
15
14
1
6
20
9
17
10
2
9
5
5
6
23
7
13
3
8
3
4
15
8
7
2
8
7
4
辺容量
供給点
需要点
分割はない
電力が供給される需要量を最大にする
24
最大分割問題
8
7
14
6
8
9
8
8 7
1
15
6
15
3
5
14 14
10 8
5 3
6
6
20
9 8
17
8
2
9
23
7 2
13
3
8
4
2
充足量：４５
15
12
8
7 4
8
7
4
辺容量
供給点
需要点
電力が供給される需要量を最大にする
25
最大分割問題
7
6
8
9
8
6
15
14
1
6
20
9
17
10
2
9
5
5
6
23
7
13
3
8
3
4
15
8
7
2
8
7
4
辺容量
供給点
需要点
電力が供給される需要量を最大にする
26
最大分割問題
8
7
17
6
8
9
8 7
8
16
6
15
3
5
14 6
10 8
5 3
6 5
1
20
6
9 8
13 11
7 2
17
2
3
2
9
4
2
8
23
充足量：49
15
13
8
7
8
7
4
辺容量
供給点
需要点
電力が供給される需要量を最大にする
27
最大分割問題
結果
• （辺容量のない）木に対してすらＮＰ困難
[伊藤 et al. ‘05]
• (辺容量のある)木に対してアルゴリズムを与えた
– 擬多項式時間
– ＦＰＴＡＳ
• 任意の誤差εについて,nとεの多項式時間である
極めてよい近似アルゴリズム
n:点数
28
最大分割問題アルゴリズム
需要点
• 入力：
– 木（需要点,供給点,辺容量）
17
• 出力：
6
– 最大分割
• 供給される需要点の需要量
が最大になる分割
• 時間計算量
– 擬多項式時間（
辺容量
5
10
5
28
25
15
7
8
4
供給点
）
n:点数
=min{22,30}=22
５＋６＋７＋４＝２２
２５＋５＝３０
29
擬多項式時間アルゴリズム
• 動的計画法
– 小さな部分解からより大きな部分解を計算する
5
8
4
3
2
10
20
10
6
7
3
10
4
2
6
5
1
14
15
7
10
5
4
4
2
30
•
5
2
6 7
3
5
10
20
2
4
2
5
7
10
6
5
31
•
2
2
7
6
3
5
10
20
5
10
4
2
5
6
5
32
5
8
4
2
10
20
3
10
6
7
3
10
4
2
6
5
1
14
15
7
10
5
4
4
2
33
5
8
4
2
10
20
3
10
6
7
3
10
4
2
6
5
1
14
15
7
10
5
4
4
2
34
23
22
5
5
8
3
2
0
1
0
4
2
1
0
7
1
0
3
4
充足量＝max{23,22}=23
2
6
8
4
1
6
5
1
5
1
4
7
1
0
6
5
2
0
1
0
7
4
2
1
0
1
0
3
4
4
2
3
2
1
6
5
1
1 4
5
7
1
0
5
4
4
2
35
time
・一つの表に対して
・高々
合計 :
で計算できる
回の表の更新を行う
36
FPTAS(Fully Polynomial-Time
Approximation Scheme)
• 完全多項式近似スキーム



０＜ε＜１なる任意の精度εに対して
最大化問題
最適解： f
近似解： f A
• f A  (1   ) f
計算時間がnと1/εの多項式になる
37
FPTAS
• 擬多項式時間アルゴリズムを変更する
Fの値まで1ずつ計算する
t
md : 最大の需要量
8
2
6
１t
7
3 10
10 4 6
20 2 5
5
4
10
1
14
15
3
7 5
10 4
4
2
38
FPTAS
最適解
t
2nt
近似解
39
FPTAS
Optimum
Approximation
md : 最大の需要量
41
FPTAS
• 時間計算量
– 擬多項式時間
FPTAS
md : 最大の需要量
42
結論
• 辺容量のある木に対する
– 分割問題
• 線形時間アルゴリズム
– 最大分割問題
• 擬多項式時間アルゴリズム
• FPTAS
を与えた.
43
課題
• より大きなグラフのクラスについて
考える.
直並列グラフ
• 計算時間量の削減.
FPTAS
44
Publication
• M. Kawabata and T. Nishizeki, “Prtitioning
trees with supply, demand and edge-capacity,”
IEICE Trans. on Fundamentals of Electronics,
Communications and Computer Science, to
appear.
45

Download Report