共同研究・競争的資金等の研究課題

本研究課題の目的は，ネットワーク内の有用な構造を検出するための数理モテルの構築と効率的な計算手法の設計である．本年度は，昨年度に引き続き，大規模なネットワークを解析するために，制約付き劣モジュラ関数最大化に対するストリーミングアルゴリズムの設計に取り組んだ．我々が提案したアルゴリズムは，入力データを定数回しか見ずに効率的に近似解を計算するものであり，メモリ効率が高くデータが大規模な場合に有用である．まず，サイズ制約付きの問題に対して，従来手法よりも高速に，理論的に最適な近似解を求めるアルゴリズムを提案した．さらに，ナップサック制約付の問題について初めて非自明な近似比解析を与えた．本成果はフランス ENS の Chien-Chung Huang 氏との共同研究である． さらに，ネットワークの中から同じ性質や構造を持つ部分（コミュニティ）を検出するための最適化モデルを提案した．ネットワーク内のコミュニティを検出する問題はグラフマイニングにおける基本的な問題である．本研究課題では，コミュニティがその内部では密なつながりを持つが外へのつながりが薄いという性質を持つことに着目し，コミュニティ検出のための新しい最適化モデルを提案した．提案モデルは，最密グラフ問題と呼ばれる組合せ最適化問題の拡張でありモジュラリティ密度最大化問題とも関連が深い．本研究ではまず，提案モデルが多項式時間で計算可能であることを示した．具体的には，線形計画問題に基づくものと最大流アルゴリズムを用いたものという2つのアルゴリズムを提案した．さらに，大規模ネットワークに適用できる，ほぼ線形時間の貪欲近似アルゴリズムを提案した．データセットを用いた計算機実験により提案アルゴリズムが効果的にコミュニティを検出できることを確認した．本成果は宮内 敦史氏（理研AIP）との共同研究であり，査読付国際会議CIKMに採択された． 昨年度の研究を発展させ，劣モジュラ関数最大化という組合せ最適化問題に対するストリーミング計算手法の開発に取り組み，一定の成果を得た．また，当初の計画通り，ネットワーク内のコミュニティ構造を見つけるための組合せ最適化モデルを提案することができた．よって計画は順調に進展していると言える. 本年度に提案した劣モジュラ関数最大化問題に対するストリーミング計算手法の有用性を検証する．計算時間や近似比等の改善の可能性や実用的な有効性の確認などを，共同研究者と協力しつつ引き続き研究を推進する．また，ネットワーク内のコミュニティ構造を見つけるための組合せ最適化モデルについて，より現実に近い状況が扱えるように提案モデルを改良し，高速・高精度な計算手法の設計に取り組む．このための情報収集や研究討論を目的として，国内外の研究集会への参加や共同研究者先への訪問を計画している．また，研究の過程で得られた理論的成果，実験結果に関する情報交換を行なうために，国内外の研究会等で発表する．

本研究では、基礎的なアルゴリズムに関する研究を行い、成果をあげた。以下に主要な２点を挙げる。 グラフの連結度を求める問題は、東西冷戦時代（つまり1950 年代）より組合せ最適化における中心的課題の一つである。以下の論文では、辺連結度に関して、初の「決定的」な「ほぼ」線形アルゴリズムを与えた。辺連結度に関する「非決定的」な「ほぼ」線形アルゴリズムは、Karger により2000 年に開発されていたが、「決定的」アルゴリズムは長年未解決であった。本論文はその最終的な解決を与えている。本論文は、コンピューターサイエンス分野の最高峰の国際学術雑誌 Journal of the ACM（ J. ACM） に掲載されている。またグラフの連結度を求める問題は、グラフの最小カットを求める問題に相当する。この最小カットを拡張するk-カット問題は、NP困難問題であることが知られているが、既存の近似アルゴリズムを大幅に更新した。 バンディット問題は、現在機械学習分野における一大分野であり、最悪ケースにおけるリグレット解析、および計算量の解析が主要課題である。またバンディット問題の中にも、組合せ最適化問題、オンライン線形計画化問題など、数多くのバリエーションがある。本研究では、１．バンディット組合せ的最適化問題に対して、最悪ケースにおけるリグレット損失の下界を改善。２．バンディットフィードバックを持つオンライン線形最適化問題に対して、オフライン線形最適化問題を解くオラクルを仮定したもとで、劣線形リグレットを達成しつつ効率的な（つまりオラクル呼び出し回数が少ない）アルゴリズムを与えた。３．バンディット問題のオンラインポートフォリオ版に対しても、最善のリグレットバウンドを与えた。 現時点で得られている成果は、計算機科学分野の国際会議ランキングで最も信頼度が高いThe Computing Research and Education Association of Australasia (CORE)において、トップにあたるCORE　A*国際会議に、11本の論文が採択され、CORE　A*に次ぐランクのCORE Aには、全部で8本の論文が採択されている。CORE A* およびCORE　Aにランクされる論文を20本近く過去2年弱で発表した事実は、当該研究分野で世界に十分認められる研究業績の生産性を表している。さらに計算機科学全体でトップのジャーナルであるJ.ACMに論文が採択され、計算機科学分野のトップ会議であるICALP’19のベストペーパーも獲得している。これらは、世界をリードするような研究成果である。 現在一番力を入れているのは「向き付きグラフマイナー理論」である。向きなしグラフマイナー理論が、多くのステップ（23論文、500ページ以上）が必要であったように、向き付けグラフマイナー理論も、今後多くのステップが必要であることは多くのグラフ理論研究者やアルゴリズム研究コミュニティに理解されている。現在の研究成果として、アルゴリズム分野のトップ会議に採用された2つの論文（SODA’19、SODA’20）は、向き付きグラフマイナー理論構築の途中経過の結果であるが、アルゴリズム研究コミュニティに高く評価されている。なおSODA’19はグラフマイナー論文VIIの一部、そしてSODA’20はグラフマイナー論文XIIIにあたる。グラフマイナー論文自体は、XXIIIまであり、本研究期間終了までは、XXまでの仕事が完了すると考えている。 グラフのトポロジー面を考慮したアルゴリズム開発は、STOC’19に代表されるような、曲面上に埋め込まれたグラフの解析が最も大きな課題である。STOC’19で開発した手法を踏まえ、この方向でも研究を進めたい。 また分散計算においても、当該分野の最大の研究課題である「マッチング問題」「独立点問題」に貢献したいと考えている。

大規模ゲノム情報は、①：長大なゲノム配列の中で一部の遺伝子変異のみが関与する「スパース性」、②：遺伝子変異数がサンプル数と比べて著しく大きい「P>>N問題」、が特徴である。遺伝統計学で扱われるヒト集団ゲノム情報は単純なグラフ構造として記述でき、即ち組合せ最適化問題として解釈可能である。本研究は、遺伝統計学と最適化理論の学際連携を通じて、大規模ヒトゲノム・臨床情報の組合せ最適化問題としての再定義を目指すものである。

本研究では，数理論理学からの計算限界解析を行い，様々な成果を得た． 具体的には，例えば，領域計算量に関して決定性と非決定いう計算モデルに能力の差を示す：任意のk=o(log n)に対して、NC[k]≠AC[k]を得た．また，単量論理回路における非多項式下界をさらなる改善を示した． さらに，重み付きの線形マトロイドパリティ問題は離散最適化分野の基礎をなす重要な問題である。この問題に対して初めての多項式時間アルゴリズムを与えた．

本研究課題では，離散・連続最適化問題が持つ組合せ的構造に着目し，その構造を有効に利用した効率的アルゴリズムの設計を行なった．離散最適化問題については，グラフ上の最適化問題から生じる詰め込み・被覆型の整数計画問題に対して，構造的グラフ理論の先進的手法を利用することでErdos-Posa性と呼ばれる組合せ的構造を明らかにし，効率的な固定パラメータ・アルゴリズムを設計した．連続最適化問題に関しては，線形相補性問題という一般的な数理計画問題に対して，整数性などの組合せ的性質の解析，および，疎性など内在する組合せ的性質を利用した効率的なアルゴリズムの設計を行なった．

定性的行列理論とは、入力の符号情報のみから形システムの定性的挙動を解析する手法であり、経済モデルなど入力数値が不確かな場合に有用である。本研究課題は、定性的行列理論の最新の成果を利用して、最適化問題に対する効率的解法を設計することを目的としている。 本研究では、最適化問題に対し符号可解性という概念を導入した。最適化問題が符号可解であるとは、入力の符号パターンから最適解の取り得る符号パターン集合が一意に定まるものをいう、昨年度までに、線形計画問題に対し、符号可解十分条件の導出と、その十分条件を満たす線形計画に対する効率的な組合せ的解法の設計に成功した。今年度は、線形相補性問題の符号可解性を議論した。まず、ある妥当な仮定を満たす線形相補性問題に対し、符号可解性に対する組合せ的な特徴付けを与えた。さらに、その特徴付けを利用して、線形相補性問題の符号可解性を判定し、符号可解ならば解を見出す効率的解法を提案した。これらの成果は、査読付き国際会議『整数計画と組合せ最適化』(IPCO)に採択され、昨年6月に発表を行なった。さらに線形計画と線形相補性問題に対する提案手法を実装し、実用的な有効性を検証した。 また、二次計画に対する符号可解性条件を考察するために、係数行列が対称行列である線形方程式の組合せ的構造を調べている。対称行列の非零構造を表す二部グラフは対称性を有しており、その種々の基本的性質も対称構造を持っている。現在、その対称構造の解明を進めている。

数理計画法とはある制約の下で最もよい解を見つけるための方法論であり,オペレーションズ・リサーチなどの様々な工学分野で必要となる.一方の組合せ的行列理論は,行列要素の正負零などの非数値情報を利用した解析手法であり,大規模な線形方程式系を解く際に有用である.本研究課題では,数理計画問題に対して,問題の持つ非数値情報を利用することでその構造を組合せ的に解析した.さらに,組合せ的行列理論の枠組みを数理計画法という応用の観点から発展させた.

工学や社会科学の諸分野における最適化の理論と応用を「離散凸パラダイム」に よって統合する研究を行った．離散凸解析の理論と応用を， 連続・離散軸，凸・非凸軸，分野横断軸，の３つの観点から整理することによって，個々の数 理的技法や応用諸問題の相互関係を明確にし，数理の深化，応用の開拓，ソフト ウェアの整備の３つの観点から研究を行い，新たな展開を達成した．とくに，数理の深化については，Ｌ凸関数最小化アルゴリズムの詳細な解析やＤＣ計画の枠組みの提示などの成果をあげた．

組合せ遷移とは「状態空間上での遷り変り」を数理モデル化・解析するアルゴリズム理論であり，その概念は，理論から応用まで多種多様な分野に現れる．本研究領域では，組合せ遷移のアルゴリズム基盤，実装技術基盤，数学基盤を構築することで，研究でも実務でも障壁なく，組合せ遷移のアルゴリズム技術を利活用するための共通基盤を構築する．本研究は計画研究C01班であり，数学を背景分野とする．特に，組合せ遷移における数学活用事例の体系的収集と組合せ遷移の研究に資する数理手法の開発を推進する．これにより，個別的にアドホックな手法で研究されていた組合せ遷移を，数学の視点から組織的に捉え直し，体系化を図る．

組合せ最適化は膨大な組合せの中から最適なものを見つけるための方法論であり実社会への応用が数多くある．本研究課題では，不確実性をもつ組合せ最適化モデルに対して，計算効率性や近似可能性を特徴付ける組合せ構造の解析を行う．情報通信・社会システム設計などの応用分野では，センサーの観測にもとづきリアルタイムで最適化することや，データを予測しつつ逐次的に最適化することなど，必要な情報が後から得られる状況下での最適化が重要となる．このようなモデルの記述が不確実・不完全な状況を扱える汎用的な組合せ最適化モデルの解析に取り組み，応用分野に有用となる新しい理論基盤を創出する．

現在の情報検索技術（GoogleのPageRank）、セキュリティ技術（Appleの(Local)　Differential Privacy）などのアルゴリズム革新は国家規模のビジネス創成につながり、現在のGAFAを作り上げた。ここで重要なのは、PageRankもDifferential Privacyもアルゴリズム、離散数学の基礎・理論研究であり、最初から応用を志向した仕事ではない点である。本研究では、このような背景を踏まえ、グラフアルゴリズム、離散数学、組合せ最適化分野での世界的な研究成果発信を目指す。またこれらを通して「人材育成」およびアルゴリズム国際共同研究拠点構築を目指す。