ブログ
計算数学セミナー（7月19日）
terui今回のご講演は，学群（部）4 年生や大学院生の方々を主な対象に，入門的解説も含めてお願いしております．多数の方々のご来聴を歓迎します．
タイトル: グレブナ基底を用いたパラメトリック整数計画アルゴリズムについて
講演者: 渋田 敬史氏（九州大学 マス・フォア・インダストリ研究所）
日時: 2013 年7 月19 日（金） 16:00〜17:00
場所: 自然系学系棟 D 棟 D814 セミナー室
概要:
パラメトリック整数計画問題とは線形制約の右辺ベクトルがパラメタになっているような整数計画問題である．コンパイラ最適化等への応用に動機付けられ，Feautrier のアルゴリズム，Verdoolaege のアルゴリズムなど種々のアルゴリズムが提案されているが，これらのアルゴリズムの時間計算量評価は難しい．
本講演では，Hosten-Thomas の代数的アルゴリズムによるパラメトリック整数計画問題求解法を紹介し, それがある意味で最も単純な解を計算することを示す.
また, アルゴリズムで中心的な役割を果たす標準対分解を単調論理関数双対化の観点から眺めることで，パラメトリック整数計画問題は $$2^{O(n(\log n+\log a_{\max}))}$$ 時間で解くことができることを示す(ただし, n は変数の数, $$a_{\max}$$ は行列の要素の最大絶対値, 行列のランクは定数とする) .
世話人: 田島 慎一，照井 章
連絡先: 照井 章 (terui at math.tsukuba.ac.jp) (at => @)
掲示・チラシはこちら:20130719-poster.pdf
