Parameterized Complexityof Sparse Linear Complementarity Problems
Hanna Sumita, Naonori Kakimura, Kazuhisa Makino(NII, ERATO)(University of Tokyo)(Kyoto university)

Linear Complementarity Problem
Input: a square matrix 　 　 　 　 　M 2 Rn⇥n , a vector q 2 Rn
Output: a vector z 2 Rn+s.t. M z + q 0, z 0

z > (M z + q) = 0• NP-hard problem [Chung 1989]• Applications: LP, Convex QP, Bimatrix game, …
2015/12/22,23

情報系 WINTER FESTA0z0+Mz + q

Goal of this work
Fact. a solution is easily found
if we know positive entries SS0+

support0+z Mz + q#candidate index sets: 2n (trivial)bound by parametersconstruct an f (parameters) · nO(1) time algo.

parameters r, c, sM

r = max. #nonzero entries
in a rowc = max. #nonzero entries
in a columnz+s0

Why sparsity?
1. Sparsity often appears in applications
2. Previous works on (parameterized) complexity of sparse problems

Our results & previous works
input

M

outputgenerals : support sizezs+0general

NP-hardW[2]-hard[Chung 1989][Estivill-Castro, Parsa 2009]r= 2)
NP-hard (r(r=2)

row-sparsity[Sumita, Kakimura, Makino 2015]

W[1]-hard2)
NP-hard (c == 2)

W[1]-hard

NP-hard (r ==cc ==2)2)((r + c)rcs)O(cs) · nO(1)ccol-sparsity

r&c

No polynomial kernal

Remark:It is not easy to extend previous results, but we can use the ideaOn k-Submodular Relaxation

岩政 勇仁（東京大学）
平井 広志（東京大学）

2015/12/22-23@情報系 WINTER FESTA1

k-劣モジュラ関数
定義（k-劣モジュラ関数）

defg : {0, 1, . . . , k}n ! R [ {1} が k-劣モジュラ関数, g(x) + g(y)g(x u y) + g(x t y)n(x, y 2 {0, 1, . . . , k} )[A. Huber and V. Kolmogorov (2012)](x u y)i :=(0min{xi , yi }(x t y)i :=(0if 0 6= xi 6= yi 6= 0,max{xi , yi } otherwise.

if 0 6= xi 6= yi 6= 0,otherwise.

2

k-劣モジュラ関数
劣モジュラ関数や双劣モジュラ関数の拡張• k-劣モジュラ関数が多項式時間で最小化可能か不明（オラクルモデル）• VCSPモデルでは，多項式時間で最小化可能•[J. Thapper and S. Živný (2012)]

少ない変数の関数の和で表される大きな関数の最小化を扱うモデル(2変数関数，3変数関数)（例）
g(x1 , x2 , x3 , x4 , x5 ) = g1 (x2 , x4 ) + g2 (x1 , x2 ) + g3 (x3 , x4 , x1 ) + g3 (x2 , x1 , x1 )3

k-劣モジュラ緩和[I. Gridchyn and V. Kolmogorov (2012)]nf : {1, . . . , k} ! R [ {1}g : {0, 1, . . . , k}n ! R [ {1}定義（k-劣モジュラ緩和）
g が f の k-劣モジュラ緩和
def ・ g が k-劣モジュラ関数,・ g|{1,...,k}n = f4

問題設定
Given :nf : {1, . . . , k} ! R [ {1}Problem :f の k-劣モジュラ緩和は存在するか？

5

本研究の成果
1. k-劣モジュラ緩和可能な関数の必要十分条件を導出
2. 組合せ的なアルゴリズムを構築
・VCSPモデル・FPTアルゴリズム
・最大化アルゴリズムに対して有用6

Proximal DC Algorithm for Sparse Optimization

Katsuya Tono
(Univ. of Tokyo)
Joint work with:
Jun-ya Gotoh (Chuo Univ.)
Akiko Takeda (Univ. of Tokyo)

Sparse Optimization
Redundantinformation＝＋0ResponseHigh dimensional data

Noise

WeightL0-constrained Problem

Approach:smooth loss function

min. f (x)
s.t.

x 0k

# nonzero elements•

L1 relaxation (convex)•Nonconvex approx.

•DC reformulationDC (= Diﬀerence of Convex functions) Approachrelaxation

L0-constrainedproblemmin.

L1 regularizationf (x) + x 1 x(t+1) = prox

f (x)

s.t.

· 1

sum of top-k elements

x 0|||x|||k )( x 1ksubgradientx1f (x(t) ) + s(x(t) )
LL
PDCA

(t)

DC reformulationequivalent(Proximal DC Algorithm)

600

PDCA

500

0.7

ISTA

400

0.6

300

0.5

0.01

100

2468

10 12 14 16 18

Iteration

00

0.03
0.02

200

0.40.04

Time (s)# nonzero elements

Objective value

0.80ISTA1(t)xf (x(t) )L246810 12 14 16 18

Iteration

00246810 12 14 16 18

Iteration

発表者：宮内 敦史（東京工業大学）

A. Miyauchi & Y. Kawase:“What Is a Network Community?
A Novel Quality Function and Detection Algorithms,”
CIKM 2015.
We introduce a novel quality function communitude• communitude maximization problem• two-phase linear-time algorithm• experimental evaluation

Scom(S) = √e[S]m −(D[S]
2m(D[S]2m)2()2 ()2 )1 − D[S]2m