組合せ的制約をもつ線形システムの解法

点击翻译按钮获取中文摘要

本研究の目的は，組合せ的制約をもつ線形システムを解くアルゴリズムの構築と理論解析である．2022年度では，研究課題に関連して，以下の成果を得た．共通するのは，線形計画問題の最適解を利用しているという点である．まず，密グラフを検出する問題において確率的な解（部分グラフに対する確率分布）を求める問題を扱った．時系列データなどの複数レイヤーをもつネットワークにおいて，どのレイヤーでも共通して密である部分を検出する問題は計算量的に難しいことが知られている．それでも何らかの解を求める必要があるときに用いる手段のひとつは，確率的な解を利用することである．本研究では，線形計画問題を用いて確率的な解を求めるアルゴリズムを提案した．この確率的な解は，効率的に計算できる「ネットワークの密っぽさ」の指標として用いることができる．この結果は国際会議WSDM2023で発表済みである．また，2018年度に行ったロバスト組合せ最適化問題に対する近似アルゴリズムの改良を行った．改良には，2019年度に行った公平割当問題のアルゴリズム設計手法を用いる．具体的には，線形計画問題に対する楕円体法と組合せ最適化問題の近似アルゴリズムを組み合わせることで，以前の研究で与えたアルゴリズムよりも良い理論保証をもつアルゴリズムを得られた．これらの結果は英文論文誌に投稿中である．他にも，エージェントに割り当て可能な財の集合に制約がある場合などの公平割当に関する研究を行い，国際会議で発表予定である．