B01: 代数的および確率的手法による離散構造の限界の究明

B01
代数的および確率的手法による
離散構造の限界の究明
タイトルスタイルの編集
テキストスタイルの編集
伊東
利哉
上野修一
東京工業大学
東京工業大学
" -近似独立置換族
1.
" -近似 k-限定独立置換族： (" ; k) -独立置換族
置換族
F ò Sn が (" ; k) -独立であるとは
8x 1; . . .; x k 2 [1; n ]
ôk
õ
V
Pr
ù(x i ) = yi à
i= 1
2.
8y1; . . .; yk 2 [1; n ]
1
n(nà 1)ááá(nà k+ 1)
ô
"
n(nà 1)ááá(nà k+ 1)
" -近似k-限定最小値独立置換族：(" ; k) -最小値独立置換族
8X ò [1; n] s. t. j X j ô k
8x 2 X
Pr [minf ù(X ) g = ù(x) ] à
1
jX j
ô
"
jX j
• 下界： (" ; k) -独立（一般分布）
n(n à 1) ááá(n à k + 1)
" < 1
n(nà 1)ááá(nà k+ 1)
"+ 1
"õ 1
jF j õ
• 非構成的上界： (" ; k) -独立（一様分布）
ð
ñ
k ln n
j F j = O " 2 n(n à 1) ááá(n à k + 1)
• 構成的上界： (" ; 2) -独立（一様分布）
全ての n = pm à 1 に対して
j F j = dí =" e n(n à 1)(1 + o(1))
í =
4
x2 à x + 1 :
GF(pm ) 上既約
6
x2 à x + 1 :
GF(pm ) 上可約
• 構成的上界： (" ; 3) -独立（一様分布）
全ての n = pm に対して
j F j = dí =" e n(n à 1)(n à 2)(1 + o(1))
í =
6
x2 + x + 1 :
GF(pm ) 上既約
12
x2 + x + 1 :
GF(pm ) 上可約
• 非構成的上界： (" ; k)-最小値独立（一般分布）既知
ð
jF j = O
àn áñ
2
k
" 2 log k
• 下界： (" ; k) -最小値独立（一様分布）既知
p áá
à 2à
j F j = Ò k 1 à 8"
• 下界： (" ; k) -最小値独立（一様分布）本研究
ò
ó
q
log(n=k)
"
jF j = Ò k
• 下界： (" ; k) -最小値独立（一般分布）本研究
ð
jF j = Ò
ð
jF j = Ò
k log(n=k)
" 2 log(1=" )
2
ñ
k log(n=k)
" log(1=" )
ñ
QoS (Quality of Service) オンラインアルゴリズム
B
ááá
ááá
.
p1
p2
..
ááá
pm
..
.
q
転送パケットの優先度
の総和を最大化
•
キューに格納されたパケットが破棄可能：
•
キューに格納されたパケットが破棄不可能：パケット破棄不可能モデル
Q
P
パケット破棄可能モデル
: 優先度集合 P 上のパケット列全体
•
パケット破棄不可能モデル
8A 2 DPT 9 û 2
OPT ( û)
A ( û)
•
õ 1+
Q
f 1;ëg
1
ë ln ( ë ëà 1)
パケット破棄可能モデル
8A 2 DPT 9 û 2
OPT ( û)
A ( û)
õ 1:514
Q
[0;ë ]
商品価格設定問題
i1
i2
i3
i4
i1
i5
C5 : 20
80 C1
C1 : 80
i5
i2
C3 : 120
90 C2
120 C 3
C4 : 50
50 C4
20 C5
C2 : 90
i4
i3
予算額（既知）
i1
i2
i3
i4
i5
C1
C2
C3
C4
C5
20
40 60
30
50
80
0
90
50
0
220
40
30 50
20
60
0
80
90
0
20
190
30
40 50
20
80
80
90 120
50
20
360 (最大)
1. 各商品の価格を安く設定
商品は多く売れるが店の売り上げが伸びない．
2. 各商品の価格を高く設定
商品があまり売れず店の売り上げが伸びない．
商品価格設定問題
各顧客の予算額が既知の場合に，店の売上げを
最大化するような各商品の価格を求める問題
ＮＰ困難
次数 d が限定された場合
既知
2分グラフ
1
2
一般グラフ
1
4
本研究
à
á
1
1
2 1 + d2
à
á
1
1
4 1+ d
予算額比γが限定された場合（γ＝最小予算額／最大予算額）
既知
一般グラフ
1
4
本研究
2+ í
8
1
1
2 á2à í
0ô í <
2
3
2
3
ô í ô 1
重み付き乱択最適選好マッチング
m
C1
C2
n C3
C4
C5
a
e
a
c
e
d
b
d
b
c
e c
c a
e b
a d
b d
M1
b
d
c
e
a
M2
a > C1
e > C2
d < C3
c = C4
b > C5
M1 > M2
最適選好マッチング(popular matching)
C1
C2
C3
C4
C5
e
b
a
c
d
Ｍが最適選好マッチングであるとはＭ＜Ｍ’となる
Ｍ’が存在しないこと
乱択最適選好マッチング
m
a 1
n b 1
c 1
a
b
c
M1
2
2
2
a
b
c
1
2
3
M1 > M4
1
0
a
b 1
c -
0
-
3
3
3
M2
1 a
2 b
3 c
M3
M1 < M5
0
a 1
b
c
0
0
1
1
a
b
c
1
2
3
a
b
c
M4
1
2
3
M4 > M5
1
0
0
1
a
b
c
M5
1 a
2 b
3 c
M6
1
2
3
M1 > M4 > M5 > M1
1 最適選好マッチング×
0
顧客が単一グループのとき (既知)
• m=n > 1:42
Pr [ 最適選好マッチングを持つ ] = 1 à o(1)
• m=n < 1:42
Pr [ 最適選好マッチングを持つ ] = o(1)
顧客が k õ 2 グループのとき (本研究)
• n 4=3=m = o(1)
Pr [ 最適選好マッチングを持つ ] = 1 à o(1)
• m=n 4=3 = o(1)
Pr [ 最適選好マッチングを持つ ] = o(1)
B01 代数的および確率的手法による離散構造の限界の究明
3次元回路設計に関する研究目標


3次元チャネル配線問題の計算複雑度の解明
3次元チャネル配線の実用的なアルゴリズムの開発
タイトルスタイルの編集
可逆回路設計に関する研究目標
テキストスタイルの編集


可逆回路の故障検出問題の計算複雑度の解明
サイズO ( log N )の完全テスト集合を生成するアルゴ
リズムの開発
於 2005年6月開催全体会議
B01 代数的および確率的手法による離散構造の限界の究明
3次元チャネル
W
top layer
タイトルスタイルの編集
H
テキストスタイルの編集
bottom layer
D
( W, D, H ) - channel
B01 代数的および確率的手法による離散構造の限界の究明
3次元チャネル配線
タイトルスタイルの編集
テキストスタイルの編集
( 4, 4, 5 ) - channel
B01 代数的および確率的手法による離散構造の限界の究明
3次元チャネル配線
タイトルスタイルの編集
テキストスタイルの編集
( 4, 4, 5 ) - channel
B01 代数的および確率的手法による離散構造の限界の究明
3次元チャネル配線問題
タイトルスタイルの編集
入力
正の整数 W, D, H, 端子の集合：
T ＝ { (ai , bi , H)|1 ≤ ai ≤ W, 1 ≤ bi ≤ D, 1 ≤ i ≤ p }
∪{ (cj , dj , 1)|1 ≤ cj ≤ W, 1 ≤ dj ≤ D, 1 ≤ j ≤ q },
テキストスタイルの編集
T のネットへの分割： N1,・・・, Nm
質問
ネットの集合 { N1,・・・, Nm} は
(W, D, H) – channel 内で配線可能か？
B01 代数的および確率的手法による離散構造の限界の究明
3次元回路設計に関する研究成果
タイトルスタイルの編集
• 3次元チャネル配線問題はNP完全である
テキストスタイルの編集
B01 代数的および確率的手法による離散構造の限界の究明
( W, 1, H ) – CHANNEL ROUTING
タイトルスタイルの編集
テキストスタイルの編集
線形時間配線アルゴリズム [ Dolev etd., 1981 ]
B01 代数的および確率的手法による離散構造の限界の究明
( W, 2, H ) - CHANNEL ROUTING
タイトルスタイルの編集
テキストスタイルの編集
計算複雑度は未解決 [ Johnson, 1982 ]
B01 代数的および確率的手法による離散構造の限界の究明
可逆ゲート
t
c1
c1 c2
t  c1 t
c1
t
c1
c2
t  c1c2
t
タイトルスタイルの編集
0-CNOT
2-CNOT
1-CNOT
c1
c1
テキストスタイルの編集
c2
c2
ck
t
ck
t  c1c2 ...ck
k-CNOT
B01 代数的および確率的手法による離散構造の限界の究明
ＣＮＯＴゲートの万能性
タイトルスタイルの編集
x1
x1
x2
x 2 テキストスタイルの編集
1
x1x2 1  x 1x 2
B01 代数的および確率的手法による離散構造の限界の究明
可逆回路の故障検出問題
タイトルスタイルの編集
入力可逆回路，整数B.
テキストスタイルの編集
質問配線の縮退故障に対する大きさB以下
の完全テスト集合は存在するか？
B01 代数的および確率的手法による離散構造の限界の究明
可逆回路設計に関する研究成果
タイトルスタイルの編集
• 可逆回路の故障検出問題はNP完全である
テキストスタイルの編集
B01 代数的および確率的手法による離散構造の限界の究明
関連する研究成果
タイトルスタイルの編集
• 直並列グラフの3次元直交描画
• ハイパーキューブの3次元レイアウト
テキストスタイルの編集
• 可逆回路の縮退故障に対する完全テスト集合
の大きさの下界
タイトルスタイルの編集
Thank you
テキストスタイルの編集

Download Report