Theory and algorithms for combinatorial optimization under uncertainty

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

本研究課題では，不確実性をもつ組合せ最適化モデルに対して，計算効率性や近似可能性を特徴付ける組合せ構造の解析を行なうことを目指す．期間初年度である今年度は，関連する文献や国際会議における研究動向の調査，および，海外の共同研究者との情報交換を行なった．そして，基本的な組合せ最適化問題であるマッチング問題について入力データの不確実性が計算効率性に与える影響を解析した．具体的には，二部グラフにおいて，頂点が確率的（ポアソン過程）に出入りする状況で最大マッチングを求める問題の解析に取り組んだ．このモデルでは，各頂点の滞在時間は指数分布にしたがうが，滞在中どの時点でマッチングを形成するかが，マッチングを求めるアルゴリズムの性能に関わる．本研究では，貪欲法など基本的なマッチングアルゴリズムを考えることで，各頂点の待ち時間とアルゴリズムの性能の関係を解析した．この成果は，マッチングマーケットの解析を動機としており，ウェブとインターネット経済に関する査読付き国際会議The 17th Conference on Web and Internet Economics(WINE2021)に採択された．また，この研究成果を中心に，2022年度には離散数学とその応用に関する日洪シンポジウムにおいて招待講演を行なった．そのほかにも，オンラインマッチング問題の拡張であるオンラインタスク割り当て問題に対するオンラインアルゴリズムの提案や，関連研究である組合せ遷移の研究成果を得た．