組合せ最適化問題の列挙アルゴリズムの構築

報告者は、今年度の科学研究費の支援により、以下の研究実績をあげることができた。1.重み付き多数決ゲームの指数計算をSurvey論文にまとめ発表した。発表論文中には、既存の研究の他、著者らによるオリジナルのアルゴリズムも掲載した。この論文は、ゲーム論,統計,確率、組合せ最適化と、多数の分野を含む充実した構成である。2.ヒッチコック問題の双対問題多面体の端点を、多項式遅延で列挙するアルゴリズムを構築し、現在、論文にまとめている。ヒッチコック問題の双対問題多面体の端点は、既存のアルゴリズムを利用して、列挙することは可能であるが、多項式遅延での列挙は実現されておらず、理論的計算量の側面からみると、興味深い結果であると思う。3.2値マトロイドのサーキット列挙問題を継続して研究中である。また、並行して、組合せ最適化問題に対するグレブナー基底の列挙問題の研究を行っている。今年度の業績をまとめると以下のとおりである。・査読付き論文1本(他、投稿中2本)、口頭発表2件。

報告者は、今年度の科学研究費の支援により、以下の研究実績をあげることができた。1.重み付き多数決ゲームの指数計算をSurvey論文にまとめ発表した。発表論文中には、既存の研究の他、著者らによるオリジナルのアルゴリズムも掲載した。この論文は、ゲーム論,統計,確率、組合せ最適化と、多数の分野を含む充実した構成である。2.ヒッチコック問題の双対問題多面体の端点を、多項式遅延で列挙するアルゴリズムを構築し、現在、論文にまとめている。ヒッチコック問題の双対問題多面体の端点は、既存のアルゴリズムを利用して、列挙することは可能であるが、多項式遅延での列挙は実現されておらず、理論的計算量の側面からみると、興味深い結果であると思う。3.2値マトロイドのサーキット列挙問題を継続して研究中である。また、並行して、組合せ最適化問題に対するグレブナー基底の列挙問題の研究を行っている。今年度の業績をまとめると以下のとおりである。・査読付き論文1本(他、投稿中2本)、口頭発表2件。