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

About关于研究室

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

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

Research研究课题

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

※示意图

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

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

※示意图

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

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

Voices学长学姐的评价

评价基于在读（或曾在读）学生的个人经历，不代表研究室官方观点。评价的有无或数量不代表对研究室的评价。

对于接受采访的学生，无论内容如何，我们可能会赠送谢礼（价值1,000日元的礼品）。