数理情報工学／ 2018 重み付き線形マトロイド交差問題に対する代数的アルゴリズム

研究概要

線形マトロイド交差とよばれる集合族のなかで、重みの和が最大になる集合を求める問題は、多くの組合せ最適化問題の一般化となっている。本研究では、この問題を行列式の次数を利用して、入力のサイズに関する多項式時間で解くアルゴリズムを作成した。

自分の知識不足を感じながらも、先行研究の論文や平井先生とのミーティングを通して、研究が進んでいく楽しさを味わうことができました。