10/16(月): 伊藤賢一(東大・数理) 「たいりんぐ三題噺」 10/23(月): 浅野泰仁(東大・理・情報科学) 「1品種1パス流(unsplittable flow)の近似アルゴリズムについて」 1996年Kleinbergによって提案された1品種1パス流(unsplittable flow) 問題は, 古典的多品種流(multicommodity flow)問題の 拡張で, 各品種について需要を満たすのに使うことのできるパスは1本だけである. さらに, 1品種1パス流問題は容量付きネットワーク上での辺素パス (edge disjoint paths)問題と 考えることもでき, 高バンド幅ネットワークの接続要求問題, 光ネットワーク, スケジューリング問題, VLSIの配線問題などの基本的モデルとして用いられている. 1品種1パス流問題の実行可能性判定問題はNP-完全である. したが