多品種流問題に対する幾何学的アプローチ(<特集>最先端を目指す若手研究者達)
スポンサーリンク
概要
- 論文の詳細を見る
最大重み多品種流問題は最大流問題の一般化であるが,整数枝容量であっても一般には整数最適解を持たない.しかし,フローが出入りする点の集合とその上の重みによっては整数最適解を持つ.そのため,どのようなときに整数最適解を持つのかについて長年研究されてきたが,最近になって,この疑問が解明された.その際に用いられた手法は,幾何学的な手法で,距離のタイトスパンやトロピカル多面体と呼ばれる幾何学的概念が重要な役割を果たす.特に,それらの幾何学的構造が最適解の構造を陽に表す.このような手法は,組合せ最適化の手法として例を見ないものであり,本稿では,それを紹介する.
- 2011-01-01