分野別セミナー

講演者: 藤重 悟 先生(京都大学 数理解析研究所)


講演題目：線形計画問題へのアプローチ --- LP-Newton法


概 要：
多面体を特徴付けるパラメタとして、端点数やファセット数などがあるが、辺ベクトル(辺方向ベクトル)の数も重要である。劣モジュラ構造に関連して現れる"基多面体"の辺ベクトル数は関連の次元 n の２乗で抑えられるが、端点数は n! でファセット数は 2^n のオーダにまでなる。辺ベクトル数が多項式で抑えられる多面体を"辺多項式多面体"と呼ぶ。線形計画問題に関係して現れる"ゾノトープ"もその典型的な例の一つである。
本講演では、直線と辺多項式多面体の交わりの端点を見出すためのアルゴリズムである"LP-Newton法"ならびに関連する話題についてお話しする。