修士論文 要旨

多重マトロイド制約最適化問題の近似アルゴリズムと整数性ギャップ
数理情報学専攻 48176207

腰高 拓美

指導教員

岩田 覚 教授める.

1 はじめにマトロイドは組合せ最適化における基本的な構造でk-マッチオイド問題は次のように定義される.

あり, 多くの組合せ最適化問題がマトロイド制約上の最定義 2 (k-マッチオイド問題). 入力として m(≥ k)適化問題として記述することができる. 線形関数最適化

個のマトロイド Mi = (Ui , Ii )(i = 1, ..., m) と, 集合問題の制約条件として与えられるマトロイドが一つあ

U = U1 ∪ · · · ∪ Um の各要素の重み関数 w : U → R>0

るいは二つの場合については多項式時間アルゴリズムが与えられる. ただし任意の要素 u ∈ U に対し, #{i ∈が知られている. 一方で制約条件として与えられるマ{1, ..., m} | v ∈ Ui } ≤ k が成り立つとする. このときトロイドが三つ以上の場合, 最適解の計算が NP 困難でU の部分集合 S で, 任意の i について S ∩ Ui ∈ Ii を満∑たすものの中で,u∈S w(u) が最大となる S を求める.

ある.

k 個のマトロイドを制約条件とする k-マトロイド交叉問題に対し, 重みなしの場合 Lee–Sviridenko–Vondrák[3] が k2 + ϵ-近似, 重 み つき の 場 合 Lee–Sviridenko–Vondrák [2] が k − 1 + ϵ-近似のアルゴリズムを与えk-マトロイド交叉問題の線形計画緩和として次の線形計画問題を考える:

maximizew(u)·x(u)u∈U∑

た. これらのアルゴリズムは近傍探索を用いている. 一方で線形計画緩和を用いた近似アルゴリズムも存在し,∑subject tox(u) ≤rMi (S), ∀i ∈ {1, ..., k}, ∀S ⊆ U ,u∈S

重みなしの場合 Lau–Ravi–Singh [1] が k − 1-近似, 重x(u) ≥ 0, ∀u ∈ U .

みつきの場合 Linhares–Olver–Swamy–Zenklusen [4]が k = 3 に対し 2-近似のアルゴリズムを与えた.

k-マ ト ロ イ ド 交 叉 問 題 の 一 般 化 と し て 定 義 で きる k-マッチオイド問題に対しても, Lee–Sviridenko–

同様に k-マッチオイド問題の線形計画緩和として次の線形計画問題を考える:

maximizeVondrák [3] が重みなしの場合 k2 + ϵ-近似, 重みつきの場合 k = 2 に対し 32 -近似のアルゴリズムを与えた. こ
こで前者は近傍探索, 後者は線形計画緩和を用いたアル∑u∈Usubject to∑

し, 重みなしの k-マッチオイド問題に対する k − 1 + k1 -x(u) ≤rMi (S), ∀i ∈ {1, ..., m}, ∀S ⊆ Ui ,u∈Sx(u) ≥ 0, ∀u ∈ U.

ゴリズムである.
本研究では線形計画緩和を用いたアルゴリズムに注目

w(u)·x(u)ただし, rMi は各マトロイド Mi の階数関数である.
一般に線形計画緩和問題と元問題の間には整数性近似アルゴリズムを示した. さらに入力のマトロイドがギャップと呼ばれる値が定義される.

ラミナーマトロイドの場合には, 重みつきの問題が持つ

定義 3 (整数性ギャップ). 最大化問題の最適値を Opt,整数性ギャップを示した.

線形計画緩和問題の最適値を LP とする. このとき線形LPと定義する.
計画緩和問題の整数性ギャップ = sup Opt

2 問題設定ここで sup は対象の最大化問題のすべての入力に対しk-マトロイド交叉問題は次のように定義される.ての上限を表す.

定義 1 (k-マトロイド交叉問題). 入力として共通の台集

先行研究のうち, 線形計画緩和を用いたアルゴリズ合を持つ k 個のマトロイド Mi = (U, Ii )(i = 1, ..., k)ムの近似比は全て整数性ギャップと等しくなっている.と, 各要素の重み関数 w : U → R>0 が与えられる. こLee–Sviridenko–Vondrák [3] は k-マトロイド交叉問題のとき U の部分集合 S で, 任意の i について S ∈ Iiの整数性ギャップは k − 1, k-マッチオイド問題の整数を満たすものの中で,性ギャップは k − 1 + k1 であるという予想を与えた.

∑u∈S w(u) が最大となる S を求多重マトロイド制約最適化問題の近似アルゴリズムと整数性ギャップ (腰高 拓美)

3 研究成果本研究では次の補題を示した.
補題 1. k-マッチオイド問題の線形計画緩和問題の端点解 x について, x は全ての成分が 0 のベクトル, またはある要素 u ∈ U が存在して x(u) ≥ k1 のどちらかが成り立つ.

いる. k-ハイパーグラフ b-マッチング問題は制約条件をマトロイドとして表すと分割マトロイド上の k-マッチオイド問題と等価であるが, ラミナーマトロイドは分割マトロイドを一般化した構造になっている.

4 今後の課題
今後の課題としては次の二つが挙げられる. 一つ目の
課題はラミナーマトロイド上の重みつき k-マトロイド

補題 1 の結果を重みなし k-マトロイド交叉問題に対交叉と k-マッチオイド問題に対し, 整数性ギャップと等する Lau–Ravi–Singh [1] のアルゴリズムと組合せるこしい近似比の多項式時間近似アルゴリズムを構成するとで, 次の定理が得られる.

ことである. Parekh–Pritchard [5] は k-ハイパーグラ定理 1. 重みなし k-マッチオイド問題の整数性ギャッ
プは k − 1 + k1 で, 近似比 k − 1 + k1 の多項式時間近似アルゴリズムが存在する.
本研究では定理 1 の結果は重みつき 2-マッチオイド問題に対する Lee–Sviridenko–Vondrák [3] のアルゴリズムを含む枠組みになっていることも示した.

フ b-マッチング問題に対し, 整数性ギャップの証明だけではなく等しい近似比の多項式時間近似アルゴリズムを構成している. このことから定理 2 の結果についても多項式時間近似アルゴリズムを構成する余地が存在すると考えられる.
二つ目の課題はラミナーマトロイドに限らない任意のマトロイド上の重みつき k-マトロイド交叉と k-マッ

一方で 2-マッチオイド問題を除く重みつきの問題にチオイド問題に対して整数性ギャップを示すことであ対しては, マトロイドのクラスを制限することによってる. 重みつき 3-マトロイド交叉問題に対する Linhares–整数性ギャップを示した. まずラミナー集合族とラミOlver–Swamy–Zenklusen [4] のアルゴリズムはマトロナーマトロイドは次のように定義される.

イド交叉問題, すなわち k = 2 の問題において多面体の定義 4 (ラミナー集合族). 集合族 L に対し, 任意の異なる 2 つの集合 A, B ∈ L について A ⊆ B, B ⊆A, A ∩ B = ∅ のいずれかが成り立つとき, L をラミ端点が整数解となる事実に依存している. 一般の k において端点解が満たす性質を用いた証明が可能なのかについてさらなる研究が必要と考えられる.

ナー集合族と呼ぶ.

参考文献

定義 5 (ラミナーマトロイド). 有限集合 U について,[1] L. C. Lau, R. Ravi, and M. Singh: Iterative Methods
in Combinatorial Optimization, Cambridge University Press, Cambridge, 2011.
[2] J. Lee, M. Sviridenko and J. Vondrák: Submodularmaximization over multiple matroids via generalizedexchange properties, Proceedings of the 12th International Workshop and 13th International Workshop
on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, LNCS
5687, Springer-Verlag, 2009, 244–257.
[3] J. Lee, M. Sviridenko and J. Vondrák: Matroid
matching: the power of local search, SIAM Journal
on Computing, 42 (2013), 357–379.
[4] A. Linhares, N. Olver, C. Swamy, and R. Zenklusen:
Approximate multi-matroid intersection via iterativerefinement, arXiv, 2018.
[5] O. Parekh and D. Pritchard: Generalized hypergraph matching via iterated packing and local ratio,
Proceedings of the 12th International Workshop on
Approximation and Online Algorithms, LNCS 8952,
Springer-Verlag, 2014, 207–223.

その部分集合族でかつラミナー集合族である L と関数

l:L → Z≥0 が存在し, U の部分集合族 I をS ∈ I ⇔ 任意の L ∈ L について |S ∩ L| ≤ l(L)で定めると M = (U, I) はマトロイドになる. このように定義されるマトロイドをラミナーマトロイドと呼ぶ.
このラミナーマトロイド上の問題に対して, 次の定理を示した.
定理 2. 入力のマトロイドがラミナーマトロイドの場
合, 重みつき k-マトロイド交叉問題の整数性ギャップは

k − 1 で, 重みつき k-マッチオイド問題の整数性ギャップは k − 1 + k1 である.
定理 2 の結果は, Parekh–Pritchard [5] が k-ハイパー
グラフ b-マッチング問題の整数性ギャップの証明に用いたアルゴリズムおよび手法を拡張したものになって