値付き制約充足問題と離散凸解析の融合と深化

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

・値付き制約充足問題の重要な特殊クラスである2次VCSPにおいて，離散凸解析の理論を適用することで，新たな多項式時間可解なクラスを導いた研究（平井広志准教授，室田一雄教授，Stanislav Zivny准教授との共同研究）が，論文誌ACM Transaction on Algorithmsに採択された．・2×2型分割行列というシンボリック行列（＝要素に変数が含まれている行列）のランクを求める組合せ的な多項式時間アルゴリズムを構築した．（平井広志准教授との共同研究）この結果は，査読付き国際会議21st Conference on Integer Programming and Combinatorial Optimization (IPCO 2020)に採択された．・Lendl, Peis, Timmermansが近年導入した「重み付きマトロイド交叉問題のロバスト版」を，離散凸解析の視点で捉え直し，背後に潜む数理構造を明確にした．さらに．線形関数最適化である重み付きマトロイド交叉から，非線形関数最適化である付値マトロイド交叉への拡張が，多項式時間可解性を損なわないことを明らかにした．（高澤兼二郎准教授との共同研究）この結果は，査読付き国際会議16th Annual Conference on Theory and Applications of Models of Computation (TAMC 2020)に採択された．