A submodular function is a discrete analogue of a convex function. It enables us to describe a large class of practical problems and arises in substantial fields, including graph theory, economics and information theory. Since 1970s, research on submodular functions has revealed fundamental structures of efficiently solvable combinatorial optimization problems, and that area is still growing. One of the most exciting developments of recent years is a breakthrough in combinatorial algorithms for submodular function minimization (SFM). In this dissertation, we consider several problems with submodular structures, and design efficient algorithms with the aid of classical methods and state-of-the-art techniques.

First, we deal with a line search problem in a polyhedron associated with a submodular function. For this fundamental problem, we develop the first strongly polynomial algorithm by combining a fully combinatorial algorithm for SFM of Iwata and the parametric search method of Megiddo.

Next, we show that the recent SFM algorithm of Orlin can be embedded within a parametric minimization framework successfully, which results in a faster algorithm for parametric submodular function minimization. We also give a new application to the measurement of robustness of a submodular system.

Subsequently, we examine convex optimization problems over submodular constraints, and clarify the connections between some apparently different problems. In addition, we develop an efficient and general method for convex optimization over submodular constraints using parametric SFM algorithms.

Lastly, we treat convex relaxations for combinatorial optimization problems with submodular penalties. We propose the use of simple and recent algorithms for non-smooth convex optimization due to Nesterov. Our algorithms can be used to design fast and simple approximation algorithms for the original problems.

本論文は,劣モジュラ関数を用いて定義される様々な連続最適化問題に対して,組合せ的なアルゴリズムの設計と解析を行っている.劣モジュラ関数は,離散最適化を始めとして,ゲーム理論,情報理論,待ち行列理論など,数理工学の諸分野において基礎的な諸概念を記述する際に自然に現れる集合関数であり,凸関数の離散版に当たる.特に,離散最適化においては,最小木問題や最大流問題のように,効率的に解くことのできる組合せ最適化問題の多くが何らかの形で劣モジュラ関数と関係していると言われている.

本論文では,劣モジュラ関数最小化の組合せ的アルゴリズムの開発に代表される近年の研究成果を踏まえた上で,劣モジュラ関数を用いて定義される多面体上の連続最適化問題や劣モジュラ関数を費用関数に含む組合せ最適化問題の連続緩和問題などの連続最適化問題に対して,組合せ的な多項式時間アルゴリズムを開発している.

本論文は,7章からなる.第1章では,本論文の背景となる劣モジュラ最適化の概要を紹介した後,本論文の主要な成果を概説している.

第2章は,数学的な準備に当てられている.特に,凸解析からの必要事項と劣モジュラ関数を用いて定義される多面体の組合せ論的性質を述べた後に,劣モジュラ関数最小化の枠組みを解説している.

第3章は,劣モジュラ関数を用いて自然に定義される多面体である劣モジュラ多面体中で,初期点と移動方向が与えられた際に,何処まで移動できるかを計算する直線探索問題に対する強多項式時間アルゴリズムを与えている.この問題に対して,Newton法を用いた弱多項式時間アルゴリズムが知られていた.また,特殊な方向に限っては,劣モジュラ関数最小化に帰着できる.しかし,一般の方向ベクトルに対して強多項式時間アルゴリズムが存在するかどうかは,未解決問題であった.本論文では,Megiddoが1983年に提案したパラメトリック探索技法の枠組みを適用し,劣モジュラ関数最小化の完全に組合せ的なアルゴリズムを援用することで,最初の強多項式時間アルゴリズムを設計し,計算複雑度に関する問題を解決した.設計されたアルゴリズムの計算量自体は高い次数の多項式となっており,実用に供するには不適であるが,理論的な意義は大きく,今後の計算量の改善が期待される.

第4章は,強射と呼ばれる関係で結び付けられた劣モジュラ関数の列に対して,それぞれ劣モジュラ関数の最小値を計算するパラメトリック劣モジュラ関数最小化問題を扱っている.劣モジュラ関数最小化問題に対する現時点で最速の強多項式時間アルゴリズムは, 2007年にOrlinによって提案されたアルゴリズムである.本論文では,本質的にこれと同じ計算量で,強射列中のすべての劣モジュラ関数の最小値が計算できることを示し,最小比問題やロバスト性解析への応用を示している.

第5章は,劣モジュラ関数を用いて定義される基多面体上の分離凸型費用関数の最小化問題を扱っている.特に,二乗和の最小化が対数和の最大化と等価な問題となるなど,これまで別種の問題として扱われていた問題の間の等価性を明らかにしている.二乗和の最小化は,1980年に藤重によって提案された辞書式最適基を求める問題と等価であることが知られていた.2007年に, Jain-Vazirani が, ある種の市場均衡問題を対数和の最大化として定式化して,効率的なアルゴリズムを与えたが,本論文の結果は,この問題が,既に解決済みの問題と等価であることを示している.定義域の特殊性ゆえに,様々な最適化問題が同じ最適解を導くという知見は,目的関数の設定が自明ではない現実問題の取り扱いに関する示唆に富んでいる.

第6章は,劣モジュラ関数を費用関数に含む施設配置問題や集合被覆問題を扱っている.これらの問題は,NP困難であり,効率的な厳密解法は原理的に存在し得ないと予想されている.そこで,連続緩和問題を解き,得られた解を何らかの方法で丸めることによって,近似解を得ることを考える.本論文では劣モジュラ関数のLovasz拡張として得られる凸関数を費用関数に含む連続緩和問題を導入し,Nesterovによるスムーズ最小化法や劣勾配法といった最新の凸最適化手法を援用することによって,連続緩和問題に対する近似解法を提案している.さらに,丸め方に関する具体的な手続きを示すことによって,劣モジュラ関数を費用関数に含む施設配置問題に対する定数近似比のアルゴリズムを与えている.劣モジュラ関数の凸関数との密接な関係が指摘されて久しいが,その関係を効率的なアルゴリズムの設計に活かした研究成果は稀であり,さらなる発展が期待される.

最後に第7章では,本論文の成果を簡潔に纏めると共に,今後の研究課題を提示している.

本論文の研究成果は,劣モジュラ関数の組合せ多面体論に立脚しつつ,Megiddoのパラメトリック探索やNesterovのスムーズ最小化法のように連続最適化の分野で発展してきた手法を積極的に取り入れて,新たな結果を導いている.いずれの結果も最適化手法に関する知見を確実に前進させており,数理情報学の発展に大きく貢献するものである.

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる.