An Exponential Time Algorithm for
Read-k-times Branching Program Satisfiability
Junichi Teruyama (NII, JST ERATO)[On going]
joint work with Atsuki Nagao(Univ. of Electro-Communications), Kazuhisa Seto(Seikei Univ.)

Branching Program (BP)◦ Computation Model◦ Representation of f : {0, 1}n → {0, 1}

root0-sink

1-sinkx1 x2 x3 : Output
0 0 0 : 10 0 1 : 00 1 0 : 10 1 1 : 11 0 0 : 0
1 0 1 : 01 1 0 : 11 1 1 : 0

An Exponential Time Algorithm for
Read-k-times Branching Program Satisfiability
Junichi Teruyama (NII, JST ERATO)[On going]
joint work with Atsuki Nagao(Univ. of Electro-Communications), Kazuhisa Seto(Seikei Univ.)root

Branching Program (BP)◦ Computation Model◦ Representation of f : {0, 1}n → {0, 1}

BP Satisfiability (BP SAT)
◦ Find an assignment which reaches to the 1-sink◦ NP-Complete◦ Exhaustive Search: 2n time
◦ Can we solve in timesuper-polynomial speed-up
exponential speed-up01

super-polynomial speed-up
𝛿General

Time: 2𝑛−𝑛 , 𝛿 = 𝛿 𝜖 , Size: 𝑛2−𝜖 , Space: Exp.
[Chen, et al. (CCC2014)]

Read k-times

exponential speed-up when input size is linear
1
Time: 2 1−𝜇 𝑐 𝑛 , 𝜇 𝑐 = Ω 2𝑘−1−1

Read-Twicelog

k-IBDD

Input size: 𝑐𝑛, Space: Exp.
[Nagao, Seto, T. (WADS2015)]

2-IBDD
NP-Complete
k-OBDD

Read Once
OBDD

P𝑐

Read-Twice

2-IBDDsuper-polynomial speed-upGeneral𝛿

Time: 2𝑛−𝑛 , 𝛿 = 𝛿 𝜖 , Size: 𝑛2−𝜖 , Space: Exp.
[Chen, et al. (CCC2014)]

Read k-times

𝟐𝒌𝒏 −𝛀 𝒏 / 𝒌

Time:𝟐,Size: poly(𝑛), Space: Poly.
exponential speed-up !!
Time:𝟐𝟓𝒏/𝟔 ∼ 𝟏. 𝟕9𝒏 , Size: poly(𝑛), Space: Poly.
exponential speed-up when input size is linear
1
Time: 2 1−𝜇 𝑐 𝑛 , 𝜇 𝑐 = Ω 2𝑘−1−1

Read-Twicelog

k-IBDD

Input size: 𝑐𝑛, Space: Exp.
[Nagao, Seto, T. (WADS2015)]

2-IBDD
NP-Complete¾ Key Idea
Pk-OBDD
9Decomposing
Read-k-times
BPs
Read Once
9Partial Assignment
OBDD
9Exhaustive Search for Disjoint Sets𝑐

Read-Twice

2-IBDD

Modeling dominance networks
with intrinsic node weights
複雑ネットワーク・地図グラフグループ
特任研究員
阿部 真人

Figure 1
Dominance
networks in ant workers
C1

C2

C3

High rank

Low rank

C4

Directed Acyclic Graph (DAG)
C5

C6

Shimoji, Abe, Tsuji, Masuda (2014, J. Roy. Soc. Interface)Generative model
Q. How do the networks emerge from interactions?
Assumption

・Each individual has w (e.g., strength or body size)
・Probability of adding links depends on w and wʼ

G(w, w′ )w′w…
t = 0

t = 1

t = 2

G(w,w’)

1.0
0.8
0.6
0.4
0.2
0.0
0.0 0.2 0.4 0.6 0.8 1.0

Evolving modelw-w’Network generated from model
Empirical

Other quantities✓DAG✓degree distribution✓relationship between rank and out-degree✓random DAG with same degree sequnce

Model

Other species✓wasp✓hyaena✓elephantMonotone 𝒌-Submodular Function Maximization
with Size Constraints
Naoto Ohsaka (UTokyo), Yuichi Yoshida (NII)

Task: select a single set of items of a specific size
Goal: maximize a submodular set function 𝑓
Easy to optimize (approx. ratio ≈ 𝟎. 𝟔𝟑)

Consider more complex situations
𝑿𝟏𝑿𝟐 𝒄𝒂𝒅𝑿𝟑𝒆𝒇𝒃𝑒𝒂 𝒃 𝒄 𝒅 𝒆 𝒇𝒙(𝑒) 𝟏 𝟑 𝟐 𝟏 𝟎 𝟑

Select multiple subsets Assign multiple kinds of items

We adopt 𝒌-submodular functions

Our contributions
Approximation algorithms
For monotone 𝒌-submodular function maximization
under size constraints①Total size constraint
Given a total budget 𝐵
for 𝑘 kinds of items#+#+#=𝐵Approx. ratio = 1/2# function eval. =𝒪(𝑘𝑛𝐵) Greedy strategy
𝒪 𝑘𝑛 Random sampling#②Individual size constraint
Given a budget 𝐵𝑖
for each kind of items= 𝐵1 , # = 𝐵2 , #Approx. ratio = 1/3# function eval. =𝒪(𝑘𝑛𝐵) Greedy strategy𝒪(𝑘 2 𝑛) Random sampling= 𝐵3