講演資料 - ERATO 河原林巨大グラフプロジェクト

ERATO 河原林プロジェクト
ハイライト_Group2
• 水野貴之（JSTさきがけ）
• 山口勇太郎（岩田CREST）
• 長尾篤樹（渡辺科研費新学術領域）
河原林ERATO ネットワークアルゴリズムグループ
• Andre van Renssen
• Jean-Francois Baffier
• Man-Kwun Chiu
• 田村祐馬
• 畑中達彦
ビッグデータ統合利活用のための次世代基盤技術の創出・体系化さきがけ
金融ビッグデータによるバブルの早期警戒技術の創出
水野貴之国立情報学研究所・JSTさきがけ
概要
【目的・手法】バブルのナウキャストは可能か？
・バブルとは単なる急激な成長ではなく，実体
経済から乖離した過剰投機による上昇である
集中投機による不平等の拡大を観測
【株式・不動産バブル検出】
・人気の銘柄に投機マネーが集中するために
企業業績の差以上に株価の差が生まれる
・人気の物件に投機マネーが集中するために
物件の質の違い以上に価格に差が生まれる
【暴落・暴騰のキッカケの検出】
・ネガティブな情報ほど短期間に報じられる
・ニュースの「新規性」「話題性」を抽出
【金融ショックの波及】
・４取引先まで金融ショックが波及
金融
ビッグデータ
30万社の株価
1億社の財務諸表
100万件の不動産
3億記事のニュース
集中投機の
可視化
バブル
非バブル
日本の不動産バブル
上海株式市場での株価格差
[Ohnishi, Mizuno, et al, IJMP2012]
上海ショック（２００８）
米国の所得格差
ITバブル崩壊(2000)
ウォール街大暴落（1929）
ブラックマンデー（1987）不動産バブル崩壊（2008）
Packing Non-zero 𝐴-paths via Linear Matroid Parity
Yutaro Yamaguchi
(Univeristy of Tokyo)
Non-zero 𝐴-paths
O 𝑉
5
-time
[Chudnovsky, Cunningham,
Geelen 2008]
[Y. 2014]
Mader’s S-paths
𝑠
𝑡
Menger’s
𝑠–𝑡 Paths
O 𝑉
-time
via L.M.P.
[Schrijver 2003]
[Cheung, Lau, Leung 2014]
Non-bipartite
Matching
Bipartite Matching
2.373
On Weighted Problems
Partly
Extendable
Non-zero 𝐴-paths
[Y. 2015]
Mader’s S-paths
Polytime
via Weighted L.M.P.
[Iwata 2013][Pap 2013]
𝑠
𝑡
Menger’s
𝑠–𝑡 Paths
Non-bipartite
Matching
(cf. Min-Cost Flow)
(cf. Hungarian Method)
Bipartite Matching
[Edmonds 1965]
𝑘-IBDD SAT に対する効率的なアルゴリズム
脊戸和寿（成蹊大学）
照山順一（NII）
長尾篤樹（電気通信大学）
• 分岐プログラムと呼ばれる計算モデルに対するSAT問題（これをBP-SATと
呼ぶ）は一般にNP完全である.
• 分岐プログラムの部分クラス（𝑘-IBDD）に対し2𝑛 より真に速いアルゴリズム
を提案．
2-IBDD
2-OBDD
SAT問題が
NP完全
こちらは
多項式時間
解決可
𝑘-IBDD SAT に対する効率的なアルゴリズム
脊戸和寿（成蹊大学）
照山順一（NII）
長尾篤樹（電気通信大学）
BP class BP size
Chen, et al.
Any BP
(CCC 2014)
𝑛2−𝜖
Running time for BP SAT
𝛿
𝑛−𝑛
2
,𝛿
Space
= 𝛿(𝜖)
Exp.
𝛼
Our result 𝑘-IBDD
1
𝑛−𝑛
poly(𝑛) poly 𝑛 ⋅ 2
, 𝛼 = 𝑘−1
2
1
(𝑘 ≥ 2)
Poly.
poly 𝑛 ⋅
poly 𝑛 ∙ 2
Our result 𝑘-IBDD
𝑐𝑛
2
(𝑘 ≥ 2) 𝑐:const 𝜇 𝑐 = Ω
1−𝜇 𝑐 𝑛
1
𝑘−1 −1
2
(log 𝑐)
Exp.
Constrained Routing
Routing in a Network with Obstacles
André van Renssen
André van Renssen
Constrained Routing: Routing in a Network with Obstacles
Constrained Routing
t
s
André van Renssen
Constrained Routing: Routing in a Network with Obstacles
Constrained Routing
t
s
André van Renssen
Constrained Routing: Routing in a Network with Obstacles
Results
First routing algorithm on constrained θ-graphs
Improved routing algorithm for Delaunay triangulation
André van Renssen
Constrained Routing: Routing in a Network with Obstacles
Extended Multiroute Flow For Multilink Attack Networks
Vorapong Suppakitpaisarn, Hidefumi Hiraishi, Hiroshi Imai
Jean-François Baffier
Post-Doc in NARC group (since May 2015), [email protected]
December 22-23, 2015
Baffier, Suppakitpaisarn, Hiraishi, Imai
Extended Multiroute Flow For MLA Networks
December 22-23, 2015
1/3
Multilink Attack network flow problems (MLA)
Classical max-flow
2
2
s
2
2/2
4
t
s
MLA-reliable flow
2/2
s
Baffier, Suppakitpaisarn, Hiraishi, Imai
t
2/4
MLA-robust flow
3/4
2/2
2/2
2/2
2/2
4
4/4
2/2
t
s
3/4
2/2
0/2
Extended Multiroute Flow For MLA Networks
4/4
t
0/4
December 22-23, 2015
2/3
Multilink Attack network flow problems (MLA)
Classical max-flow
2
2
s
2/2
(4)
2
s
t
MLA-reliable flow
2/2
s
Baffier, Suppakitpaisarn, Hiraishi, Imai
t
2/4
MLA-robust flow
3/4
2/2
2/2
2/2
2/2
4
4/4
2/2
t
s
3/4
2/2
0/2
Extended Multiroute Flow For MLA Networks
4/4
t
0/4
December 22-23, 2015
2/3
Multilink Attack network flow problems (MLA)
Classical max-flow
2
2
s
2/2
(4)
2
s
t
MLA-reliable flow
2/2
s
Baffier, Suppakitpaisarn, Hiraishi, Imai
t
2/4
MLA-robust flow
3/4
2/2
2/2
2/2
2/2
4
4/4
2/2
t
s
3/4
2/2
0/2
Extended Multiroute Flow For MLA Networks
4/4
t
0/4
December 22-23, 2015
2/3
Multilink Attack network flow problems (MLA)
Classical max-flow
2
2
s
2/2
(4)
2
s
t
MLA-reliable flow
2/2
s
Baffier, Suppakitpaisarn, Hiraishi, Imai
t
2/4
MLA-robust flow
3/4
2/2
2/2
2/2
2/2
4
4/4
2/2
t
s
3/4
2/2
0/2
Extended Multiroute Flow For MLA Networks
4/4
t
0/4
December 22-23, 2015
2/3
Our Contributions/Results
Multiroute flow is an approximation to MLA-robust and MLA-reliable
We Extend Multiroute Flow (EMRF) to parametric non-integer number of route
h using restricted max-flow. Solves MLA-flow problems for a category of
networks.
Experiments on random-shape networks, grids, and complete networks shows
that EMRF solves about 97% of instances.
Deterministic lower bound and heuristic upper bound. The gap between both
bounds is about 3% on those networks.
Complex networks are hard (come to see the poster!)
Baffier, Suppakitpaisarn, Hiraishi, Imai
Extended Multiroute Flow For MLA Networks
December 22-23, 2015
3/3
Navigating Weighted Regions with Scattered
Skinny Tetrahedra
Man-Kwun Chiu
[email protected]
National Institute of Informatics
Joint work with Siu-Wing Cheng, Jiongxin Jin and Antoine Vigneron
S.W. Cheng, M.K. Chiu, J. Jin, A. Vigneron
Navigating Weighted Regions
Problem Definition
Weight ωτ ∈ [1, W ].
Vertex v = (x, y ) ∈ [−N, N]2 .
P
cost(P[vs , vd ]) = simplex τ ωτ kP ∩ τ k.
S.W. Cheng, M.K. Chiu, J. Jin, A. Vigneron
Navigating Weighted Regions
Previous Result
Find a (1 + ε)-approximate shortest path.
Previous result : O Knε−2.5 log nε log3 1ε .
S.W. Cheng, M.K. Chiu, J. Jin, A. Vigneron
Navigating Weighted Regions
Previous Result
Find a (1 + ε)-approximate shortest path.
Previous result : O Knε−2.5 log nε log3 1ε .
Aspect Ratio = R/r
A tetrahedron is skinny if its aspect ratio is > ρ.
S.W. Cheng, M.K. Chiu, J. Jin, A. Vigneron
Navigating Weighted Regions
Previous Result
Find a (1 + ε)-approximate shortest path.
Previous result : O Knε−2.5 log nε log3 1ε .
Aspect Ratio = R/r
A tetrahedron is skinny if its aspect ratio is > ρ.
S.W. Cheng, M.K. Chiu, J. Jin, A. Vigneron
Navigating Weighted Regions
Our result
If skinny tetrahedra are distributed sparsely, the running time
is linear in n.
T
S.W. Cheng, M.K. Chiu, J. Jin, A. Vigneron
Navigating Weighted Regions
1
Approximablity of
the Independent Feedback Vertex Set
Yuma Tamura, Takehiro Ito, Xiao Zhou
(Tohoku University)
Independent Feedback Vertex Set problem (IFVS)
In this problem, we wish to find a minimum-size
independent set 𝐹𝐹 such that 𝐺𝐺 − 𝐹𝐹 is a forest.
Input:
simple undirected graph 𝐺𝐺
2
Independent Feedback Vertex Set problem (IFVS)
In this problem, we wish to find a minimum-size
independent set 𝐹𝐹 such that 𝐺𝐺 − 𝐹𝐹 is a forest.
Input:
simple undirected graph 𝐺𝐺
minimum-size
Deleting independent
set of three vertices
results in a forest
3
FVS and its known result
Feedback Vertex Set problem(FVS)
we wish to find a minimum-size vertex subset
such that 𝐺𝐺 − 𝐹𝐹 is a forest.
• It is known that the feedback vertex set problem
admits a 2-approximation algorithm on general
graphs
How about
IFVS?
4
5
Our results
Theorem 1
Unless P = NP, there is no poly-time 𝒏𝒏𝟏𝟏−𝜺𝜺 -approximation
algorithm for IFVS for any fixed 𝜀𝜀 > 0
even for planar bipartite graphs.
𝑛𝑛 : # of vertices of a graph
Theorem 2
For bipartite graphs, there is a poly-time 𝚫𝚫 − 𝟏𝟏
-approximation algorithm for IFVS,
where Δ is maximum degree of an input graph.
The Fixed Parameter Algorithms
for List Coloring Reconfiguration Problem
Tatsuhiko Hatanaka
Takehiro Ito
Xiao Zhou
(Tohoku University)
2015/12/22
情報系 WINTER FESTA
1
(Vertex) 𝑘-coloring
To color all vertices of a graph using at most 𝑘 colors such
that every two adjacent vertices have different colors.
𝑘=4
color set
2015/12/22
4-coloring
情報系 WINTER FESTA
2
List coloring: Generalization of 𝑘-coloring
Each vertex 𝑣 has a set 𝐿(𝑣) (a list) of allowed colors.
𝐿-coloring
2015/12/22
情報系 WINTER FESTA
3
Transformation of 𝐿-coloring
We wish to transform initial into target as follows:
(1) One can recolor only a single vertex at a time.
(2) At each step, an obtained coloring
must be an 𝑳-coloring.
?
initial
2015/12/22
target
情報系 WINTER FESTA
4
Transformation of 𝐿-coloring
We wish to transform initial into target as follows:
(1) One can recolor only a single vertex at a time.
(2) At each step, an obtained coloring
must be an 𝑳-coloring.
“reconfigurable”
initial
2015/12/22
target
情報系 WINTER FESTA
5
LIST COLORING RECONFIGURATION problem
Input Graph 𝐺
𝐺, 𝐿
Output
List 𝐿(𝑣) for each 𝑣 𝐿-colorings 𝑓0 , 𝑓𝑟
𝑓0
𝑓𝑟
YES / NO (Are 𝑓0 and 𝑓𝑟 reconfigurable?)
⇒ YES
2015/12/22
情報系 WINTER FESTA
6
Known results and our results
Known result
PSPACE-complete even for the case 𝑘 = 4, where 𝑘 is the
number of colors in the lists [BC07].
Our result
FPT algorithms for several graph classes with respect to
the parameter 𝑘.
 split graph
 cograph
 their generalizations
 1, 𝑞 -colorable
 bounded modular-width
2015/12/22
情報系 WINTER FESTA
7

Download Report