重み付きマトロイド交わり問題に対する厳密解法と近似解法(ACM-SIAM Symposium on Discrete Algorithms, SODA 2016)

垣村 尚徳
東京大学
Chien-Chung Huang (チャルマース工科大学)
神山 直之 (九州大学)
ERATO感謝祭 Season III

2016年8月

概要
 マトロイド交わり問題 (定義はのちほど)
 効率的に計算ができる基本的な組合せ最適化問題

成果１: 重み付きマトロイド交わり問題の新しい解法
 擬多項式時間(最大重みに依存)だが, 重みが小さいと最速
 アイデア：マッチングに対する重みを分解する手法を拡張
 二部グラフ [Kao-Lam-Sung-Ting 01] 一般 [Huang-Kavitha 12, Pettie 12]

成果２: 高速な近似アルゴリズム
 最適解を計算するよりも高速 重みの分解 + スケーリング[Duan-Pettie 14]

2

二部グラフのマッチング ‥ 仕事の割り当ては仕事 A を出来る

働き手

仕事

人と仕事のペアを作る

 マッチング

AA

B

B

CCD

DEE
働き手

仕事

最大マッチングを求めたい

3

二部グラフ・マッチングの制約の言い換え

端点を共有しない辺集合

マッチングでない各頂点から高々ひとつ選ぶ

各頂点から高々ひとつ選ぶ

4

二部グラフ・マッチングの制約の言い換え

端点を共有しない辺集合

各グループから高々１つ選ぶ

各グループから高々１つ選ぶ

頂点の隣接関係 = グループ

5

6

二部グラフのマッチングの言い換え
入力: 辺集合S上の制約

制約を表す部分集合の族
制約を表す部分集合の族

目的: 2つの制約をみたす最大サイズの集合 J

s.t.

各制約はマトロイドを用いて表現可能
各グループから高々１つ選ぶ

各グループから高々１つ選ぶ

7

マトロイド 交わり 問題
入力: ２つのマトロイド

制約を表す部分集合の族
制約を表す部分集合の族

目的: 2つの制約をみたす最大サイズの集合 J（共通独立集合）

s.t.

マトロイド

マトロイド

マトロイド：線形独立性の一般化

有限集合S 上の部分集合族
8で以下の性質を持つものの要素を独立集合という 独立集合の部分集合は独立⇒
でならば例
 各グループから高々1 つ選ぶの要素 e を I に足せる

マトロイド：線形独立性の一般化

有限集合S 上の部分集合族
でよい性質を持つものの要素を独立集合という

 行列の線形独立な列ベクトルの族

A

列の添え字集合で，対応する列ベクトルが線形独立となるもの

 グラフの森をなす辺部分集合の族
辺部分集合で森を成すもの

9

10

マトロイド交わり の例
 ２つのグラフの交わり [Gabox-Xu89, Gabow-Stallman85]
 トラス構造解析，電気回路解析などへの応用 ([Recski 89] など)

辺部分集合で2つのグラフで森を成すもの
辺集合に1対1対応がある

 2つの行列の交わり ネットワーク符号化などへの応用[Cunningham86, Gabow-Xu96, Harvey07,09, Cheung-Lau-Leung14]

列の添え字集合で，２つの行列で線形独立となるもの

AB重み付きマトロイド交わり問題
入力: ２つのマトロイド
各要素 e  S に非負整数重み we
目的: 最大重みの共通独立集合 Js.t.
 重み付きの問題の例
 二部グラフの最大重みマッチング (各辺に重み) (各辺に重みがある) ２つのグラフの交わり (各列に重みがある) ２つの行列の交わり

11重み付きマトロイド交わり問題
入力: ２つのマトロイド
各要素 e  S に非負整数重み we
目的: 最大重みの共通独立集合 Js.t.

 多項式時間アルゴリズム
Edmonds(1970) , Aigner-Dowling (1971), Cunningham (1986),
Gabow-Xu (1996), Lawler (1970/71), Iri-Tomizawa (1976)
Frank (1981), Brezovec-Cornuejols-Glover (1986), Fujishige-Zhang (1995)
Shigeno-Iwata (1995), Gabow-Xu (1996), …

12

13

本研究の動機
重み付き と 重み無し の計算量の違いを知る
 重み無しのアルゴリズムを使った高速化

τ：集合が独立かを判定する計算量 重み付き：遅い 増加道を用いる解法:

O(nr 2  )[Frank(1981), Brezovec-Cornuejols-Glover (1986), etc]

 重み無し：速い 高速化： O ( nr 1.5  ) [Cunningham 86]

n : 台集合 S の大きさ
r : マトロイドのランク(最大独立集合の大きさ)

成果: 重み付マトロイド交わり問題の厳密解法

14

W 個の重み無しの問題に分解可能
 W:最大重み 計算時間：O(W nr 1.5  )重み無しアルゴリズム [Cunningham 86]

 W が小さいと速い

if W  o min  r ,n log r   r  先行研究との比較:
 増加道を用いるもの: O ( nr2 ) Frank(1981), Brezovec-Cornuejols-Glover (1986), etc

 スケーリング:O(n 2 r log(rW )  )

 Fujishige-Zhang (1995), Shigeno-Iwata (1995), Gabow-Xu (1996)

15

応用: 特殊なマトロイドの場合
W 個の重み無しの問題に分解可能 一般の場合:O(W nr 1.5  )[Cunningham 86]

 特別なマトロイドには特別なアルゴリズム
先行研究
 2つのグラフ:

O (n r log2 r log(rW ))O(W n r log r )[Gabow-Xu 89]

 2つの行列:O(W nr1.38[Gabow-Xu 89]

O (nr1.77 log(rW ))[Gabow-Xu 96]) [Harvey 09]

O(W 1 nr 1.38 poly log(nW ))最大重みW が小さい場合に先行研究より高速[Harvey 07]

成果2: 近似アルゴリズム

16

W 個の重み無しの問題を解くと最適解
スケーリング(cf [Duan-Pettie 14])

O ( 1 log r ) 個の重み無しの問題を解くと (1   ) 近似解
 具体的には
 一般:

 グラフ:
 行列:

O  1 log r  nr 1.5 [Cunningham 86]

O( 1 log r  n r log r )[Gabow-Xu 89]

O (e -1 logr × nr1.38 )[Harvey 09]

成果2: 近似アルゴリズム

17

W 個の重み無しの問題を解くと最適解
スケーリング(cf [Duan-Pettie 14])

O ( 1 log r ) 個の重み無しの問題を解くと (1   ) 近似解

Cf) 多項式可解な問題に対する近似アルゴリズム
 最大マッチング Duan-Pettie14 など

 最大流問題
 Christiano-Kelner-Madry-Spielman-Teng11
 Kelner-Lee-Orecchia-Sidford14 など

厳密解法
マトロイドを修正して重み無し問題を解く

マッチングに対する重みを分解する手法を拡張
二部グラフ [Kao-Lam-Sung-Ting 01]
一般グラフ [Huang-Kavitha 12, Pettie 12]

アイデア: 重み分割 [Frank 1981]
 重みwを2つに分割: w  w1  w2w

w1w2
S

アルゴリズム i = W,…,1 に対して以下を繰り返す
 w1 と w2 を使って 新しいマトロイドとを定義
 新マトロイド上で最大サイズの共通独立集合J を求める
 J をもちいて w1 と w2 を更新

191回目の反復： i = W のとき
w1w2

 初期値： w1 = 0 と w2 = w
 重みが  Wの要素

 もとのマトロイドのみに着目とを用いて
 サイズ最大の共通独立集合を求める

20

1回目の反復： i = W のとき
w1

w2

 初期値： w1 = 0 と w2 = w
 重みが  Wの要素

 もとのマトロイドのみに着目とを用いて
 サイズ最大の共通独立集合を求める
 w1とw2の更新
 Frank81と似た方法

21

22i 反復目
w1

w2

 重みが

 i の要素のみに着目

 w1 と w2を用いて新しいマトロイドを定義の wj-最大重み独立集合のみに着目 ( wj-最大重み基 の部分集合族 ) をへ制限したもの

23i 反復目
w1w2

 重みが

 i の要素のみに着目

 w1 と w2を用いて新しいマトロイドを定義の wj-最大重み独立集合のみに着目の中でサイズ最大の共通独立集合を求める
 w1 と w2 を更新24i 反復目
w1w2

 重みが

 i の要素のみに着目

 w1 と w2を用いて新しいマトロイドを定義
の wj-最大重み独立集合のみに着目の中でサイズ最大の共通独立集合を求める
 w1 と w2 を更新
正当性：重み分割を用いた最適性判定↓ を満たせば 集合 J は最適解
 集合 J が

上でw1-最大重み独立集合上でw2-最大重み独立集合
アルゴリズムの最終目標

w1

J :w1-最大重み独立集合w2

J : w2-最大重み独立集合

25

26

反復 i で J が満たす性質
緩和した最適性条件：
J が上でw1-最大重み独立集合
上でほぼw2-最大重み独立集合

重みw2(e) > i の要素 e のみを見ると
w2-重み最大w1

w2i+1

J : w1-最大重み独立集合

ここは見ないアルゴリズム終了時 (i = 0) → 最大重み27緩和した最適性条件：
J は上でw1-最大重み独立集合
上でほぼw2-最大重み独立集合
重みw2(e) > 0 の要素 eのみを見るとw2-重み最大w1

J : w1-最大重み独立集合w2

J : w2-最大重み独立集合

28

厳密アルゴリズムのまとめ
 i = W,…,1 に対して以下を繰り返す
 w1 と w2 を使って 新しいマトロイドとを定義
 新マトロイド上で最大サイズの共通独立集合J を求める
 J をもちいて w1 と w2 を更新

計算時間: W  O(nr1.5  )重み無しアルゴリズム [Cunningham 86]

正当性：重み分割による最適性基準
 マトロイドが特殊な場合
 もしがグラフ/行列ならば，も同様

29近似アルゴリズム：重みを丸めて厳密解法
刻み幅 δj を変えつつ厳密アルゴリズムを適用j 

For j = 1,..., log WW2j

重みを δj の倍数に丸めて 厳密アルゴリズムを適用
 i = W/2j-1,…,W/2j として以下を繰り返す
 w1 と w2 を使って 新しいマトロイドとを定義
 新マトロイド上で最大サイズの共通独立集合を求める
 w1 と w2 を δj ずつ更新

若干の修正
近似率 = (1   )まとめ：マトロイド交わり問題

30

 効率的に計算ができる基本的な組合せ最適化問題

成果１: 重み付きマトロイド交わり問題の新しい解法
 重み無しのマトロイド交わり問題 を繰り返し計算
 マッチングに対する手法の拡張
二部グラフ [Kao-Lam-Sung-Ting 01] 一般 [Huang-Kavitha 12, Pettie 12] 進展： O ( n2log(nW )  ) [Lee-Sidford-Wong15]

成果２: 高速な近似アルゴリズム
 重みの分解 + スケーリング[Duan-Pettie 14]
 さらなる改良(ほぼ線形時間近似) [Chekuri-Quanrud SODA16]