平成11年度12月 最適化とアルゴリズム研究部会
- 日時:12月4日(土) 14:00 〜 17:30
- 場所:上智大学7号館12階第1215号室
- 参加者:25名
- 発表1: 後藤 順哉 氏(東京工業大学 経営システム工学専攻)
- ``Maximization of the Ratio of Two Convex Quadratic Functions
over a Polytope''
-
あるポートフォリオ選択問題から派生した、convex-convex タイプの
2次分数計画問題は、複数の局所解を持ちうる、いわゆる大域的最適
化の問題である。本研究では、その問題に対し、分枝限定法を用いた
アルゴリズムを提示する。アルゴリズムは、1)Dinkelbach のパラメ
トリック・アプローチをベースに、2)超直方体分割アルゴリズムを
適用するものである。発表では、それらの解説と計算機実験の結果を
示す。また、応用例として、あるポートフォリオ選択問題の適用につ
いても取り上げる予定である。
(今野浩氏との共著)
- 発表2:牧野 和久 氏 (大阪大学大学院 基礎工学研究科)
- ``Partial and Multiple Transversals of a hypergraph''
-
ハイパーグラフの極小横断(Minimal transversal)を列挙することが(入力長と
出力長の)多項式時間で可能かどうかは有名な未解決問題である.この問題は,
単に数学的に面白いばかりでなく,分散システムのコテリー理論や人工知能にお
ける推論問題といった実用的な問題にも密接に関連している.
本研究では,横断の概念を一般化させた部分横断,多重横断を導入し,ハイパー
グラフの極小部分横断(あるいは,極小多重横断)を列挙する問題が上記の問題
に多項式時間還元可能であることを示す.また,部分,多重横断といった概念と
知識発掘(data mining)における frequent set などとの関係を示す.
さらに,ここで用いられた証明手法が単調多面体におけるファセット数の下限を
与えることも示す.
(Endre Boros, Vladimir Gurvich, Leo Khachiyan との共著)
SOA Home Page へ.