応用数理研究部門（牧野 和久）

About研究室について

離散的な構造を、最適化とアルゴリズムへ。

牧野研究室は、グラフ理論や組合せ論などの離散的な構造を解析し、その構造を利用した最適化やアルゴリズムを研究しています。
代表的な研究は、単調な論理関数の双対化問題です。
この問題は、数理計画、人工知能、データベース、分散システム、学習理論など様々な分野に現れる多くの問題と、多項式時間還元の意味で等価であることが知られています。
整数線形不等式系、相補性問題、オンライン最適化問題、ロバスト最適化、ゲーム理論の均衡解なども研究しています。

Research研究テーマ

グラフ理論や組合せ論などの離散的な構造を解析する研究と、その構造を利用した最適化やアルゴリズムの研究をしています。単調な論理関数の双対化問題や、推論分野の論理仮説の補完問題などに取り組んでいます。

※イメージ画像

単調な論理関数の双対化問題↗

与えられた論理積形から、それと等価な単調な論理和形を求める問題です。FredmanとKhachiyanにより準多項式時間で解けることは示されていますが、多項式時間で解けるかはまだ分かっていません。

※イメージ画像

ホーン推論での論理仮説の補完↗

推論分野の論理仮説の補完問題について、共同研究で広く信じられていた予想を覆し、最も重要なクラスであるホーン推論において、逐次多項式時間で可能であることを示しました。

Voices先輩の声

評価・クチコミは、在籍している（していた）学生個人の経験に基づくもので、研究室の公式見解ではありません。クチコミの有無や件数は、研究室の評価を表すものではありません。

インタビューに協力いただいた学生に、内容にかかわらず謝礼（1,000円分のギフト）をお渡しすることがあります。