■第16回研究会(2005年7月2日(土)14:00--18:00 東京大学 工学部6号館)の講演概要
 
14:00--15:50『木構造動的ネットワーク中の最速フロー問題と施設配置問題について』大阪大学 間々田 聡子 氏
静的ネットワークに,時間軸の概念を加えたものを動的ネットワークと呼ぶ. 本発表では,特に木構造の動的ネットワークに着目し, 与えられた供給量を与えられた出口集合へ最速に送り出すフローを求める問題 (最速フロー問題)と与えられた供給量を最速に送り出すことができるような 出口を配置する問題(施設配置問題)に対する多項式時間アルゴリズムを提案する. また,これらの問題の応用例である避難問題と関連付けながら紹介する. 本研究は,宇野毅明(NII),牧野和久(阪大),藤重悟(京大)との共同研究である.
 
16:10--18:00『容量制約付き正方形被覆問題に対する発見的解法』法政大学 野々部 宏司 氏
2次元平面上に与えられた点集合に対し,大きさの決まった正方形を最小個数用いて すべての点を被覆する問題を正方形被覆問題と呼ぶ. 正方形被覆問題は NP-困難であることが知られており,1980年代に PTAS が提案されている. 本発表では,各点はそれぞれ非負の要求量を, 正方形はすべて同じ予め与えられた容量を持つものとして 容量制約のついた正方形被覆問題を考える. この問題に対する発見的解法として,(i) 集合被覆アプローチ, (ii) メタヒューリスティクス・アプローチ,の2つを計算結果と併せて紹介する.

なお,本研究は Endre Boros(RUTCOR),茨木俊秀(関西学院大), 市川浩也(住商情報システム),宇野毅明(NII),柳浦睦憲(京大)との 共同研究である.

 
Seminars on Algorithms in Operations Research
ホーム - SAORについて - 会場案内 - 全日程 - リンク
(c) 2003-2004 SAOR All rights reserved.