修士論文 要旨

k-劣モジュラ最大化の乱択法の改良と脱乱択化

1 はじめに数理情報学専攻 48166204

大島宏希

指導教員

定兼邦彦

教授

2 k-劣モジュラ最大化の先行研究

劣モジュラ性は組合せ最適化や確率，情報理論でも現

k-劣モジュラ関数には，定義に等価な表現として次のれる基本的な性質の一つであり，劣モジュラ関数は機械定理 [8] が存在する．但し [k] = {1, 2, . . . , k} である．

学習や施設配置問題などにも現れる．たとえばグラフのカット関数やマトロイドのランク関数は劣モジュラ関数である．

定理 2. x = (X1 , ..., Xk ), y = (Y1 , ..., Yk ) ∈ (k + 1)Vに対し，(k + 1)V 上の半順序 ⪯ をdefx ⪯ y ⇐⇒ Xi ⊆ Yi (∀i ∈ [k])定義 1. 集合関数 f : 2V → R が任意の S ⊆ T ⊆V , e∈
/ T に対してf (S ∪ {e}) − f (S) ≥ f (T ∪ {e}) − f (T )を満たすとき f は劣モジュラ関数であるという．
劣モジュラ最大化は，最大カット問題や，施設配置問題を含む問題になっている．最小化が多項式時間で可能なこと [4] である一方，無制約劣モジュラ最大化は，と定める．また任意の x = (X1 , ..., Xk ) に対し∆e,i f (x) = f (X1 , ..., Xi−1 , Xi ∪ {e}, Xi+1 , ..., Xk )−f (X1 , ..., Xk )と定める．f : (k + 1)V → R が k-劣モジュラ関数であることの必要十分条件は orthant submodularity∆e,i f (x) ≥ ∆e,i f (y) (x ⪯ y, e ∈/NP 困難であることが知られている．したがってアルゴリズムは近似比改善を目的としている．またその多く

および pairwise monotonicity∪∆e,i f (x) + ∆e,i′ f (x) ≥ 0 (e ∈/Xl , i ̸= i′ )l∈[k]る, 乱択 1/2-近似アルゴリズム [2] が知られている．無制約最大化に関しては，(1/2 + ϵ)-近似には指数回の関Yl )l∈[k]は確率的アルゴリズムになっている．
現在では，二つの暫定的な集合を用いた貪欲法によ∪を満たすことである．

数値呼び出しが必要であることが示されている [3] たpairwise monotonicity は k = 1 の劣モジュラ関数にめ，これが近似比の面では最良といえる．また，上記のはない特徴である．また k-劣モジュラ関数の単調性は乱択手法を脱乱択化した，決定論的 1/2-近似アルゴリ∆e,i f (x) ≥ 0 (e ∈/ズム [1] もまた存在している．

∪Xl )

l∈[k]

k-劣モジュラ関数 [5] は劣モジュラ関数及び双劣モジュラ関数の拡張として導入された．k-劣モジュラ関数はとして定義される．これは pairwise monotonicity よりも強い条件になっている．

(k+1)V := {(X1 , ..., Xk ) | Xi ⊆ V (i ∈ [k]), Xi ∩Xj =先行研究 [6, 8] から使用されている枠組み (アルゴリ∅ (i ̸= j)} 上の関数 f : (k + 1)V → R であるが，詳細ズム 1) を考える．V の要素に 1 から n まで番号を定な定義はここでは省略し，等価な性質を次章で与える．

め，t 番目の要素を e(t) と書くこととする．いずれの先k = 2 である双劣モジュラ関数最大化アルゴリズム[6, 8] の研究を経て，一般の k に対する乱択アルゴリ
ズム [8] も示された．現在では，Iwata, Tanigawa, andYoshida [7] により，非単調な場合の乱択 1/2-近似アルk-近似アルゴリズム，ゴリズム，単調な場合の乱択 2k−1

そして単調な場合 ( k+12k + ϵ)-近似には指数回の関数値呼び出しが必要であることが示されている．

(t)行研究も，yi= ∆e(t) ,i f (s(t−1) ) ををもとに，確率分

布 {p(t) } を決定する．

3 脱乱択化
脱乱択化は，k = 1 の場合に行われた手法 [1] を，乱択単調 k-劣モジュラ最大化アルゴリズム [7] に適用できるよう拡張して行った．提案アルゴリズムは，次の定理を満たす．

k-劣モジュラ最大化の乱択法の改良と脱乱択化 (大島 宏希)

Algorithm 1 乱択 k-劣モジュラ最大化の枠組み [6, 8]
1: s ← 0 (s ∈ {0, 1, ..., k}

Vk による近似比の推移)

1

2: for t = 1, ..., n do

本研究 : k = 3 の場合
本研究 : 式 (5.20) より(k 2 + 1)/(2k 2 + 1)
単調 (アルゴリズム) k/(2k − 1)
単調 (理論上限) (k + 1)/2k
先行研究 1/2

0.9

3:{1, ..., k} 上の確率分布 {p(t) } を定める．

4:

Pr[s(e(t) ) = i] = pi なる確率の下 s(e(t) ) を決0.8

定する
5: end for

近似比(t)

0.7
0.60.5

6: return s0.4
定理 3. 提案した決定論的アルゴリズムは，単調関数

0.32kについて 2k−1-近似，k ≥ 2 である非単調関数につkいて 3k−2-近似となる．また，関数値呼び出し回数は

68k10121416

図 1. k の変化と近似比の比較．

O(n2 k 2 ) 回である．
本研究では，提案アルゴリズムの関数値呼び出し回数

41+ϵk2 +12+ϵ と書ける．図 1 は (2) から得られる近似比， 2k2 +1以外での計算量についても，解析を行った．

及び先行研究での近似比をプロットしたものである．

4 乱択法の改良{}
k + ϵk(k − 1 − ln k) ≥ (k − 1) (1 + ϵ)k + ϵ(1 + ϵ)k−2(2)

本研究では，k ≥ 3 である非単調関数について，乱択法の近似比を先行研究の 1/2 から改善した．まず，

k = 3 の場合について述べる．y1 ≥ y2 ≥ y3 とし，
β := yy21 , γ := yy31 と定める．次の分布 {pi } を考える．
β1
p1 = 1+β , p2 = 1+β , p3 = 01+γβ+γp1 = 1+β+2γ, p2 = 1+β+2γ, p3 = 02−β+γβ+γp1 = 2+β+3γ , p2 = p3 = 2+β+3γ(γ < 0)(γ ≥ 0, h(β, γ) > 0)(γ ≥ 0, h(β, γ) ≤ 0)

(1)βγ
但し h(β, γ) = 1−β−γ+ 1+γ− β+γとする．このとき，2次の定理が成り立つ．
定理 4. アルゴリズム 1 において，t = 1, . . . , n の確率分布を (1) に従って定める．このとき，アルゴリズムの出力を s，3-劣モジュラ関数 f を最大化する解を o とする．この時 E[f (s)] ≥√17−3f (o) が成り立つ．
2

この近似比は，アルゴリズム 1 の分布を工夫し，各反復での改善を評価するという，今回の枠組みでは最良になっている．
続いて，k ≥ 3 の場合について，次の定理が成り立つ．
定理 5. k ≥ 3 なる非単調 k-劣モジュラ関数について，
k2 +12k2 +1 -近似を達成する乱択アルゴリズムが存在する．

証明はアルゴリズム 1 の枠組みをもとに，実際に達成するアルゴリズムを構成して行った．提案手法では，確率分布 {p(t) } を k + 1 通りから適切に選択する．この近似比はタイトではなく，(2) を満たす最大の ϵ に対し，参考文献[1] N. Buchbinder and M. Feldman. Deterministic algorithms for submodular maximization problems. In
Proceedings of the Twenty-Seventh Annual ACMSIAM Symposium on Discrete Algorithms, pp. 392–403. SIAM, 2016.
[2] N. Buchbinder, M. Feldman, J. Naor, andR. Schwartz. A tight linear time (1/2)-approximation
for unconstrained submodular maximization. SIAM
Journal on Computing, Vol. 44, No. 5, pp. 1384–1402,2015.
[3] U. Feige, V. S. Mirrokni, and J. Vondrák. Maximizing
non-monotone submodular functions. SIAM Journal
on Computing, Vol. 40, No. 4, pp. 1133–1153, 2011.
[4] M. Grötschel, L. Lovász, and A. Schrijver. The ellipsoid method and its consequences in combinatorialoptimization. Combinatorica, Vol. 1, No. 2, pp. 169–197, 1981.
[5] A. Huber and V. Kolmogorov. Towards minimizing ksubmodular functions. In International Symposium on
Combinatorial Optimization, pp. 451–462. Springer,
2012.
[6] S. Iwata, S. Tanigawa, and Y. Yoshida. Bisubmodularfunction maximization and extensions. Technical report, METR 2013-16, The University of Tokyo, 2013.
[7] S. Iwata, S. Tanigawa, and Y. Yoshida. Improved
approximation algorithms for k-submodular function
maximization. In Proceedings of the Twenty-Seventh
Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 404–413. SIAM, 2016.
[8] J. Ward and S. Živný. Maximizing k-submodular
functions and beyond. ACM Transactions on Algorithms, Vol. 12, No. 4, pp. 47:1–47:26, 2016.