Developing Theory of Combinatorial Optimization Based on Matrix Representations

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

組合せ最適化とは，複数の離散的な選択肢の中から最も良いものを探す問題の枠組みであり，いくつかの組合せ最適化問題は各要素が多変数一次式である「線形記号行列」の階数を計算する問題として表現できる．Lovasz (1989)は，各記号の係数行列が階数2の歪対称行列であるような線形記号行列の階数を計算することで，「線形マトロイドパリティ問題」を解くことができるということを示した．この問題は線形マトロイド交叉やマッチングを含む一般的な問題である．線形記号行列の階数を計算する問題はEdmonds問題とよばれ，乱数を用いずに多項式時間で解くことが可能かどうかが計算量理論における未解決問題の一つとなっている．近年，線形記号行列の各変数を積に関して互いに非可換とみなした場合に定義される「非可換階数」を計算する「非可換Edmonds問題」は決定性多項式時間可解であることが示された．代表研究者は，本年，非可換階数を用いた組合せ最適化問題の表現に取り組んだ．線形マトロイドパリティを表現する行列の非可換階数が，問題の実数緩和版である「分数線形マトロイドパリティ」の最適値に対応するということを示した．すなわち，本行列表現において，記号を可換・非可換とみなすことは，最適化問題の許容解として整数制約をそれぞれ課す・課さないという選択と対応するということを明らかにした．さらにこの事実を基にし，分数線形マトロイドパリティを解く高速アルゴリズムを提案した．本結果は離散アルゴリズム分野のトップ会議SODAで発表した．現在フルバージョンを雑誌に投稿中である．また本年は，3本の論文を機械学習分野のトップ会議NeurIPSで発表した．これらは組合せ最適化問題の行列表現とは直接関係する内容ではないものの，本研究の遂行中に得られた組合せ最適化および線形代数に対する知見を応用したものである．