•水野貴之（JSTさきがけ） •山口 勇太郎(岩田CREST) •長尾 篤樹（渡辺科研費新学術領域）河原林ERATOネットワークアルゴリズムグループ● Andre van Renssen • Jean-Francois Baffier • Man-Kwun Chiu •田村祐馬●畑中達彦ビッグデータ統合利活用のための次世代基礎技術の創出・体系化ささがけ
水野貴之国立情報学研究所・JSTさきがけ【目的・手法】バブルのナウキャストは可能か？ ・バブルとは単なる急激な成長ではなく.実体経済から乖離した過剰投機による上昇である集中投機による不平等の拡大を観測【株式・不動産バブル検出】 ・人気の銘柄に投機マネーが集中するために企業業績の差以上に株価の差が生まれる•人気の物件に投機マネーが集中するために物件の質の違い以上に価格に差が生まれる【暴落・暴騰のキッカケの検出】 ・ネガティブな情報ほど短期間に報じられる･ニュースの「新規性」「話題性」を抽出【金融ショックの波及】 •4取引先まで金融ショックが波及ビッグデータ30万社の株価1億社の財務諸表100万件の不動産3億記事のニュ集中投機の可視化
上海株式市場での株価格差上海ショック(2008)
[Ohnishi, Mizuno, et al, IJMP2012] 139.2 139.4 139.6 139.8 140 139 Longitude 140.2 140.4米国の所得格差
Yutaro Yamaguchi (Univeristy of Tokyo) Non-zero A-paths 0(|V|5)-time [Chudnovsky, Cunningham, Geelen  2008] [Y. 2014] Mader’s S-paths 0(|V|2.373)-time via L.M.P. [Schrijver  2003] [Cheung, Lau, Leung  2014] Menger's s-t Paths Non-bipartite Matching Bipartite Matching
Non-zero A-paths Partly Extendable Mader’s S-paths [Y. 2015] Polytime via Weighted L.M.P. [Iwata 2013][Pap 2013] Menger's s-t Paths (cf. Min-Cost Flow) Non-bipartite Matching [Edmonds 1965] (cf. Hungarian Method) Bipartite Matching
脊戸和寿(成蹊大学)照山順一(NII)長尾篤樹(電気通信大学) •分岐プログラムと呼ばれる計算モデルに対するSAT問題(これをBP-SATと呼ぶ）は一般にNP完全である。 •分岐プログラムの部分クラス(k-IBDD)に対し2 nより真に速いアルゴリズムを提案.
脊戸和寿(成蹊大学)照山順一(NII)長尾篤樹(電気通信大学)
Constrained Routing Routing in a Network with Obstacles André van Renssen André van Renssen
Constrained Routing: Routing in a Network with Obstacles

André van Renssen Constrained Routing: Routing in a Network with Obstacles
André van Renssen Constrained Routing: Routing in a Network with Obstacles Results ● First routing algorithm on constrained θ-graphs ● Improved routing algorithm for Delaunay triangulation
Vorapong Suppakitpaisarn, Hidefumi Hiraishi, Hiroshi Imai Jean-François Baffier Post-Doc in NARC group (since May 2015), jf_baffier@nii.ac.jp December 22-23, 2015
December 22-23, 2015

Classical max-flow
Extended Multiraste Flow For MLA Networks
December 22-23, 2015
2 / 3
Classical max-flow
Extended Multiraste Flow For MLA Networks
December 22-23, 2015
2 / 3
Classical max-flow MLA-reliable flow
Extended Multiraste Flow For MLA Networks
December 22-23, 2015
2 / 3
Classical max-flow
Extended Multiraste Flow For MLA Networks
December 22-23, 2015
2 / 3
o 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!) Navigating Weighted Regions with Scattered Skinny Tetrahedra Man-Kwun Chiu chiumk@nii.ac.jp 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
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 ξ log ³ ξ ).
S.W. Cheng, M.K. Chiu, J. Jin, A. Vigneron
Navigating Weighted Regions

■ Find a (1 + ε)-approximate shortest path. ■ Previous result : 0 (Knε−2.5 log ξ log 3 1 ). Aspect Ratio = R/r
S.W. Cheng, M.K. Chiu, J. Jin, A. Vigneron
Navigating Weighted Regions
■ Find a (1 + ε)-approximate shortest path. ■ Previous result : 0 (Knε−2.5 log ξ log 3 1 ). Aspect Ratio = R/r
S.W. Cheng, M.K. Chiu, J. Jin, A. Vigneron
Navigating Weighted Regions If skinny tetrahedra are distributed sparsely, the running time is linear in n.
S.W. Cheng, M.K. Chiu, J. Jin, A. Vigneron
Navigating Weighted Regions
40 9,00 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 F such that G — F is a forest. Input: simple undirected graph G 2 Independent Feedback Vertex Set problem (IFVS) In this problem, we wish to find a minimum-size independent set F such that G — F is a forest. Input: simple undirected graph G Deleting independent set of three vertices results in a forest
Feedback Vertex Set problem(FVS) we wish to find a minimum-size vertex subset such that G — F is a forest. ● It is known that the feedback vertex set problem admits a 2-approximation algorithm on general graphs Our results Theorem 1 Unless P = NP, there is no poly-time n 1-ε -approximation algorithm for IFVS for any fixed ε > 0 even for planar bipartite graphs. n : # of vertices of a graph Theorem 2 - For bipartite graphs, there is a poly-time (∆ – 1) -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) 1
To color all vertices of a graph using at most k colors such that every two adjacent vertices have different colors. color set 4-coloring
Each vertex v has a set L(v) (a list) of allowed colors. L-coloring 3
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 L-coloring.うtarget
INGS WININGROUPSIN
4
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 L-coloring.
ENGS  WINTNOK  RIBSTAN
5
Input Graph G List L( v ) for each v L-colorings for fr Output YES / NO (Are f 0 and f reconfigurable?) ⇒ YES
情報をWINTER FESTA
6
Known result PSPACE-complete even for the case k = 4, where k is the number of colors in the lists [BC07]. Our result FPT algorithms for several graph classes with respect to the parameter k . □ split graph口 cograph口their generalizations ◆ (1,q)-colorable ◆  bounded modular-width 7