Computing Least Cores of Supermodular
Cooperative Game (AAAI-2017)
Daisuke Hatano(NII) and Yuichi Yoshida(NII, PFI)

Cooperative game
𝑉=𝜈()=$20 𝜈()=$9𝜈()=$20

Core: A value division 𝑥 ∈ ℝ𝑉 is in the core
if 𝑥(𝑆) ≤ 𝜈(𝑆) for all 𝑆 ⊆ 𝑉 and 𝑥 𝑉 = 𝜈(𝑉)𝑥𝑥

= $9, 𝑥

= $10, 𝑥= $11 is in the core

= $10 is not in the core

情報系 WINTER FESTA episode 3

2017/12/25,26

Computing Least Cores of Supermodular
Cooperative Game (AAAI-2017)
Daisuke Hatano(NII) and Yuichi Yoshida(NII, PFI)Supermodular cooperative game
• A characteristic function 𝜈 is supermodular• The Core of a supermodular game is nonempty
Our contributions• Analyze the following solution concepts– Strong least core
– Weak least core

• Derive explicit and concise formulations
for the strong and weak least core values
情報系 WINTER FESTA episode 3

2017/12/25,26

Coarsening Massive Inﬂuence Networks
for Scalable Diﬀusion
Analysis
大坂直人 (東京大学)

薗部知大 (NII)
藤田澄男 (ヤフー株式会社 Yahoo! JAPAN 研究所)
河原林健一 (NII)

情報拡散の単純な表現形式

Q. 最も影響力の高い集団をどのように発見するか?
e.g. マーケット戦略||影響最大化 (Inﬂuence maximizaCon)
辺確率グラフ上のアルゴリズム

我々の貢献
簡略化戦略

スケーラブルなアルゴリズム

精度保証付

10億エッジ/1時間

0.2
0.8

0.5

0.9
0.7

0.8

0.6

0.1

0.2

0.1

0.2

0.2
0.7

影響
解析

0.3

1

入力のグラフに対する解

0.6

0.6

0.3
0.9
0.7

0.4

0.7

Fast

0.2
0.44
0.73

0.6

0.5

0.4

Coarsening

0.1

Fast

0.3

≒

0.8
0.7

2－30倍の高速化

Slow

0.9
0.9

解析フレームワーク

簡約化された
グラフに対する解

確率的劣モジュラ関数の適応的最大化とそのニュース推薦への応用
小西 卓哉（NII）
共同研究者：福永 拓郎（JSTさきがけ） 藤田 澄男（ヤフー） 河原林 健一（NII）•問題：ナップサック制約付き単調劣モジュラ関数の最大化– 各アイテムが確率的に決まる状態をもつ– 状態によって目的関数とナップサック制約への貢献の両方が決まる•

本研究：理論保証がある適応的な近似アルゴリズムの提案– ユーザの反応を考慮したニュースリストの推薦に応用
ナップサック制約（e.g. 閲覧時間）

反応（選択 / スキップ）に応じて次のニュースを選ぶ
情報取得 &ナップサック制約消費選択

推薦

選択 / スキップ

ユーザ

1番目のニュース

スキップ

2番目のニュース

On Estimation of Conditional Mode Using Multiple
Quantile Regressions
Hirofumi Ohta 1

Satoshi Hara 2

1 The University of Tokyo, Graduate School of Economics, Department of Statistics, M2.
2 Osaka University, The Institute of Scientific and Industrial Research.

2017/12/26, Winter-Festa Ep.3 @NII.
Keywords: modal/quantile regression, semi-parametricestimation, dimensionality reduction.

1/2

ProblemA regression analysis for Y ∈ R and X ∈ Rp .
Estimation of Conditional mode of Y given X = x, say, modal regression.
MethodEstimate the conditional density by solving linear quantile regressions multipletimes.
Modal regression function is estimated by finding the quantile which gives themaximum of conditional densities.
Contribution
New semi-parametric modeling for modal function via conditional quantilefunction.
Advantages:
computationally stable:
no initial parameter dependencies and QR can be solved by convex linear
programming.
√statistically eﬃcient with a fast convergence rate: QR has n-consistency.
2/2

Multiple zeta values in number theory
andBell polynomials in set partition（ERATO 河原林プロジェクト 理論 G町出智也）

Bell 数 と Bell 多項式

• Bell 数 Br,k ： r 個の物を k 個に分ける方法の総数• Bell 多項式 Br,k (x1 , . . . , xr−k+1 )：ベル数の一般化


Br,k (1, . . . , 1) = Br,k .

ベル数と源氏香の図
Wikipedia (https://ja.wikipedia.org/wiki/香の図) から転載

B5,5B5,4B5== 【帚木（ははらぎ）】 =1= 【空蝉、花の宴、葵、. . .】 =B5,5 + B5,4 + B5,3 + B5,2 + B5,1

10=521/2

多重ゼータ値• Euler (1707 - 1783) により始めて研究された実数• 多項式への一般化（※ 繰り込みの手法により）ζ∗⋆ (k1 , k2 , . . . , kr ; T )


結果

∑

•

σ∈Srζ∗⋆ (kσ(1) , kσ(2) , . . . , kσ(r) ; T )（Sr ：対称群）• ベル多項式との関係
5!ζ∗⋆ (1, 1, 1, 1, 1; T ) = B5 (T, ζ ⋆ (2), 2ζ ⋆ (3), 6ζ ⋆ (4), 24ζ ⋆ (5))


ちなみにr!

=Br (0!, 1!, . . . , (r − 1)!)
2/2

Submodular maximization
with uncertain knapsack capacity
Yasushi Kawase (TITech, RIKEN AIP)Hanna Sumita (NII, ERATO)
Takuro Fukunaga (RIKEN AIP)

2017/12/26

情報系 WINTER FESTA Episode3

The knapsack constraint is uncertains. t. ∑.∈1 𝑠. ≤ 𝐶

max. 𝑓(𝑋)monotone submodular

capacity is uncertain

𝑠4 = 180(yen)𝑠; = 100𝑠9 = 140

I want to choose an item set 𝑋 maximizing my utility
But I do not know the capacity 𝐶oracleOK𝑠< = 150

The knapsack constraint is uncertains. t. ∑.∈1 𝑠. ≤ 𝐶

max. 𝑓(𝑋)monotone submodular

capacity is uncertain

𝑠4 = 180(yen)𝑠; = 100𝑠9 = 140

I want to choose an item set 𝑋 maximizing my utility
But I do not know the capacity 𝐶oracle

OKNO𝑠< = 150

The knapsack constraint is uncertains. t. ∑.∈1 𝑠. ≤ 𝐶

max. 𝑓(𝑋)monotone submodular

capacity is uncertain

𝑠4 = 180(yen)𝑠; = 100𝑠9 = 140

I want to choose an item set 𝑋 maximizing my utility
But I do not know the capacity 𝐶oracle

OKNO

OK𝑠< = 150

The knapsack constraint is uncertains. t. ∑.∈1 𝑠. ≤ 𝐶

max. 𝑓(𝑋)monotone submodular

capacity is uncertain

𝑠4 = 180(yen)𝑠; = 100𝑠9 = 140𝑠< = 150

I want to choose an item set 𝑋 maximizing my utility
But I do not know the capacity 𝐶oracle

RemoveOKNOOKYoucannot

Main results
In what order should we add the items?
policy(decision tree)

fit?

YESNO

u 𝐶 is unknown: deterministic policy s.t.
output≥ 2(1 − 1/𝑒)/21 for any capacity
optimal value (𝐶: known)u 𝐶 is stochastic: a randomized algorithm s.t.
𝔼E [output]≥ (1 − 1/ H 𝑒)/4 − 𝜀
𝔼E [optimal value]
Note: all policies & algos run in poly. time
Related work: 𝐶 is known but size 𝑠. is unknown, …

Indexing Search Trees and Applications
Sankar Deep Chakraborty
National Institute of Informatics (NII)

December 19, 2017

Joint work with Kunihiko Sadakane from The University of Tokyo

Sankardeep Chakraborty

Indexing Search Trees and Applications

Problem Definition

Sankardeep Chakraborty

Indexing Search Trees and Applications

Problem Definition

Given an undirected graph G = (V , E ) where |V | = n and|E | = m, preprocess and answer the following queries: Givenany (u, v ),Sankardeep Chakraborty

Indexing Search Trees and Applications

Problem Definition

Given an undirected graph G = (V , E ) where |V | = n and|E | = m, preprocess and answer the following queries: Givenany (u, v ),are they connected?
who is visited first in the DFS/BFS traversal of G ?
do they share ancestor/decendant relationship in DFS/BFStree? etc.

Sankardeep Chakraborty

Indexing Search Trees and Applications

Problem Definition

Given an undirected graph G = (V , E ) where |V | = n and|E | = m, preprocess and answer the following queries: Givenany (u, v ),are they connected?
who is visited first in the DFS/BFS traversal of G ?
do they share ancestor/decendant relationship in DFS/BFStree? etc.

Easy! O(1) time solution when O(n) words or O(n log n) bits
are available in the word-RAM model.

Sankardeep Chakraborty

Indexing Search Trees and Applications

Problem Definition

Given an undirected graph G = (V , E ) where |V | = n and|E | = m, preprocess and answer the following queries: Givenany (u, v ),are they connected?
who is visited first in the DFS/BFS traversal of G ?
do they share ancestor/decendant relationship in DFS/BFStree? etc.

Easy! O(1) time solution when O(n) words or O(n log n) bits
are available in the word-RAM model.
What happens with less space i.e., o(n) words? Can we still
get O(1) time query or report correctly at all?

Sankardeep Chakraborty

Indexing Search Trees and Applications

Results and Techniques

Sankardeep Chakraborty

Indexing Search Trees and Applications

Results and Techniques

It is possible to answer these queries and many more with thefollowing resource bounds.

Sankardeep Chakraborty

Indexing Search Trees and Applications

Results and Techniques

It is possible to answer these queries and many more with thefollowing resource bounds.
O(log n) query time with O(n) bits of space for sparse graphs.
O(log n) query time with O(n log log n) bits of space for densegraphs.

Sankardeep Chakraborty

Indexing Search Trees and Applications

Results and Techniques

It is possible to answer these queries and many more with thefollowing resource bounds.
O(log n) query time with O(n) bits of space for sparse graphs.
O(log n) query time with O(n log log n) bits of space for densegraphs.

Can be extended for other fundamental graph theoretic
questions along with generalizing to produce time/space trade
off results.

Sankardeep Chakraborty

Indexing Search Trees and Applications

Results and Techniques

It is possible to answer these queries and many more with thefollowing resource bounds.
O(log n) query time with O(n) bits of space for sparse graphs.
O(log n) query time with O(n log log n) bits of space for densegraphs.

Can be extended for other fundamental graph theoretic
questions along with generalizing to produce time/space tradeoff results.
Main technique: Space efficient construction of tree
partioning and time effcient algorithms for tree traversal.

Sankardeep Chakraborty

Indexing Search Trees and Applications

Results and Techniques

It is possible to answer these queries and many more with thefollowing resource bounds.
O(log n) query time with O(n) bits of space for sparse graphs.
O(log n) query time with O(n log log n) bits of space for densegraphs.

Can be extended for other fundamental graph theoretic
questions along with generalizing to produce time/space trade
off results.
Main technique: Space efficient construction of tree
partioning and time effcient algorithms for tree traversal.
Open Problem: Can we go o(n) bits with efficient (polylog)
query time?

Sankardeep Chakraborty

Indexing Search Trees and Applications

Thank You.

Sankardeep Chakraborty

Indexing Search Trees and Applications

Approximation Algorithms
for Hub-and-Spoke Network Design Problems
and Metric Labeling Problems
Yuko Kuroki Tomomi Matsui
Tokyo Institute of Technology
情報系 WINTER FESTA 2017/12/26

Key words:
operations research,combinatorial optimization,
approximation algorithms

hubhubhub

Hub-and-Spoke Network arises in real world situations such as:・airline network
・telecommunication network

We discuss a problem to findan assignment of non-hubs to hubsthat minimizes total costs.

We propose polynomial time constant ratio approximation algorithms
for hub-and-spoke network design problems and metric labeling problems.
value of an approximation solution0
objective values
𝛼 ×(optimal value)

optimal value

Hub-and-Spoke Network Design Problems

Main Result

Objective function (minimization)
𝑤𝑝𝑞 (𝑝,𝑞 ∈𝑁2

Constraints𝑖∈𝐻

𝑐𝑝𝑖 𝑥𝑝𝑖 +𝑗∈𝐻𝑖∈𝐻 𝑥𝑝𝑖 = 1

𝑥𝑝𝑖 ∈ 0,1

𝑐𝑞𝑗 𝑥𝑞𝑗 +𝑖∈𝐻𝑗∈𝐻𝑐𝑖𝑗 𝑥𝑝𝑖 𝑥𝑞𝑗 )(∀𝑝 ∈ 𝑁),(∀(𝑖, 𝑝) ∈ (𝐻 × 𝑁))

Star-Metric Case-approx. alg.

Cycle-Metric Case

Metric Labeling Problems [Kleinberg and Tardos,2002]
set 𝑃 of 𝑛 objects
set 𝐿 of 𝑘 possible labels
A labeling function 𝑓 : 𝑃 → 𝐿

・2 1 − ℎ1 -approx. alg. (ℎ #hubs)
1・(32 − 2(ℎ−1))- approx. alg.

(under the assumption of triangle inequality)

A tractable class of binary VCSPs
via M-convex intersection

平井 広志（東大）
岩政 勇仁（東大D2）
室田 一雄（首都大）Stanislav Živný（Oxford）

情報系 Winter Festa Episode3@一橋講堂
2017/12/26

A tractable class of binary VCSPs
via M-convex intersection
Binary VCSPs

ﬁnite set

Given:

Fp : Dp ! R (p 2 [r])(p, q 2 [r])Fpq : Dp ⇥ Dq ! R
Problem:

Minimize
F (X1 , X2 , . . . , Xr ) :=

X

1pr

Fp (Xp ) +X

[r] := {1, 2, . . . , r}

Fpq (Xp , Xq )1p<qr((X1 , X2 , . . . , Xr ) 2 D1 ⇥ D2 ⇥ · · · ⇥ Dr )

A tractable class of binary VCSPs
via M-convex intersection
Binary VCSPs

ﬁnite setF
どのようななら多項式時間で解けるか？
Given: Fp : Dp ! R (p 2 [r])(p, q 2 [r]) [r] := {1, 2, . . . , r}
Fpq : Dp ⇥ Dq ! R
Problem:

Minimize
F (X1 , X2 , . . . , Xr ) :=X1pr

Fp (Xp ) +X

Fpq (Xp , Xq )1p<qr((X1 , X2 , . . . , Xr ) 2 D1 ⇥ D2 ⇥ · · · ⇥ Dr )

A tractable class of binary VCSPs
via M-convex intersection
Binary VCSPs

ﬁnite setF
どのようななら多項式時間で解けるか？
Given: Fp : Dp ! R (p 2 [r])(p, q 2 [r]) [r] := {1, 2, . . . , r}
Fpq : Dp ⇥ Dq ! R
Problem:Minimize

X
X
F (X1 , X2離散凸性（M凸性）を用いて, . . . , Xr ) :=Fp (Xp ) +Fpq (Xp , Xq )1pr
1p<qr
新しい多項式時間可解なクラスを構築((X1 , X2 , . . . , Xr ) 2 D1 ⇥ D2 ⇥ · · · ⇥ Dr )