概要
劣モジュラ関数最小化問題について：
(1) $O(n M^3 \log n EO)$ の偽多項式時間アルゴリズムを提案．ただし，目的関数は整数値で，最大値はMとする．
(2) $O(n^{5/3} EO/\epsilon) $ の $\epsilon$-近似アルゴリズムを提案．
アルゴリズムを一言でいえば，最小化したい関数のLovasz拡張を（確率的）劣勾配降下法で最小化する．
しかし，Lovasz拡張の劣勾配の更新が高速であるため，1ステップが速く回せる．
(1) の場合は，Lovasz拡張の劣勾配の成分の非ゼロ要素が O(M) であることに着目し，スパースベクトルの加算時に勾配を速く更新できるアルゴリズムを考える．
(2) の場合は，スパースな確率的劣勾配で分散が十分小さいものを高速に構成する．
文献情報
- Author: D. Chakrabarty, Y. Lee, A Sidford, and S. Wong
- Conference: STOC
- Year: 2017
- arxiv
コメント
- 離散最適化を確率的凸最適化で殴った論文．近似アルゴリズムの方は構成が真に確率的なところが面白い．
概要
対称劣モジュラ関数最小化の $O(|V|^3)$ アルゴリズムを与えた論文．ただし，対称劣モジュラ関数というのは，劣モジュラ関数 $f: 2^V \to \mathbb{R}$ であって，$f(X) = f(V - X)$ が成り立つものである．
文献情報
- Author: M. Queyranne
- Conference: SODA
- Year: 1995
- URL
コメント
-
対称劣モジュラ関数のわかりやすい例は，無向グラフのカット関数である．また，fが劣モジュラ関数のとき，$g(X) = f(X) + f(V - X)$ によって対称劣モジュラ関数 $g$ を作れる．
-
「対称劣モジュラ関数最小化」とは，正確には，$|V| \geq 2$ として，空集合と全体集合を除いた $V$ の真部分集合の中で $f$ を最小化するものを求める問題である．例えば，非負重みをもつ無向グラフのカット関数の最小値は明らかに $f(\emptyset) = f(V) = 0$ であるが，そうではなくて非自明な部分の最小値を求める．
-
アルゴリズムの概要は次の通りである： まず，任意の対称劣モジュラ関数に対して，pendent pairと呼ばれる頂点のペア $(s,t)$ が存在することが知られている．ここでpendent pairというのは，$s$ を固定したとき，s-tカットの最小値が1点集合 ${ t }$ によって達成されるもののことである．このようなペアは $O(n^2)$ 回の関数呼び出しで発見することができる．Queyranneのアルゴリズムは，pendent pair発見アルゴリズムを再帰的に $n-1$ 回呼び出すことで得られる．定義から，pendent pair $(s, t)$ があるとき，最小化問題の解 $X$ は $f(X) = f(t)$ であるか，$s, t \in X$ であるかのどちらかである．前者であれば終了だが，それは判定できないので，ひとまず $t$ と $f(t)$ の値を記憶しておく．後者であると仮定すると，$(s, t)$ をまとめて1頂点だと思うことで，サイズが $n-1$ の問題に帰着される．よって，「pendent pairを見つけて結合する」という操作を残り2頂点になるまで繰り返せば，記憶した $t$ のうちどれかがminimizerになっている．
-
もともと，Nagamochi and Ibaraki (1992)の最小s-tカットアルゴリズムというものがあり，その拡張として提案されたらしい．Fujishige (2005) のsection 13にも歴史が載っている．
概要
劣モジュラ関数最小化問題で，実用上最速と噂されていたFujishige--Wolfeのアルゴリズム（最小ノルム点アルゴリズム）に擬多項式時間の保証を与えた論文．Fujishige--Wolfeは，基多面体 (base polyhedron) の上で2-ノルムの2乗が最小になる点を探すアルゴリズムである．
文献情報
- Author: D. Chakrabarty, P. Jain and P. Kothari
- Conference: NIPS
- Year: 2014
- URL
コメント
-
Chakrabarty, et al. (2014) はまず，任意の多面体に対して，Wolfeの最小ノルム点アルゴリズムの連続最適化としての収束保証を与えた．次に，最小ノルム点の連続最適化としての近似精度が $\epsilon$ ならば，そこから構成できる解の（離散最適化としての）近似精度は $2n\epsilon$ である．よって，目的関数 $f$ の値のジャンプの最小幅 $F$ よりも $2n\epsilon$ を小さくとれば最適解となる．
-
全体での計算量は $O((n^5 \gamma + n^7)F)$ になる．ただし，$\gamma$ は関数値オラクル呼び出しのコストである．ジャンプの幅 $F$ に依存しているため「擬」多項式時間である．ただし，$f$ が整数値であることが予めわかっていれば，ジャンプ幅は1で下から抑えればよい．
-
この分野の論文としては珍しく（？）計算機実験がある．強多項式時間アルゴリズムとしては2014年当時の理論最速だったIwata and Orlin (2009) のアルゴリズムと比較し，Fujishige--Wolfeの方が実計算時間が速い傾向にあることを示した．
-
2017年現在，理論的に速いアルゴリズムは [Lee+2015] や [Chakrabarty+2017] とのことらしい．後者の筆頭著者はこの論文と同じ人．
参考文献
- [Lee+2015] Lee, Sidford and Wong. Faster cutting plane method and its implications for combinatorial and convex optimization. In FOCS, 2015.
- [Chakrabarty+2017] Chakrabarty, Lee, Sidford and Wong. Subquadratic submodular function minimization. In STOC, 2017.