ISMP 2日目

2日目に聞いた講演で面白いと思ったものを紹介します．

2日目のはじめはFriedrich Eisenbrandの「Algorithmic Geometry of Numbers and Integer Programming」という招待講演でした．格子におけるMinkowskiの定理と最短ベクトル問題，ディオファントゥス近似のアルゴリズム的側面 (Eisenbrand and Rothvoss 2009)，固定次元での整数計画法 (Eisenbrand 2003, Eisenbrand and Laue 2005)，パラメトリック整数計画法に対するKannan (1992) のアルゴリズムの改善 (Eisenbrand and Shmonin 2008) などが紹介されました．個人的には楽しかったですが，専門が遠い人にとってはペースの速い話だったかもしれません．でも，隣にいたHさんは面白かったと言っていたので，そうでもなかったのかもしれません．

近似アルゴリズムのセッションでDongdong Geが「Geometric Rounding」について話をしました．いわゆるdependent roundingの話で，multiway cutに対するBertsimas et al. '99, Calinescu et al '98，metric labelingに対するKleinberg and Tardos '99を簡単に解説して，どれも単体中の点をいずれかの頂点に丸めることであると見ることで，(ある意味で)より幾何的な丸め法を提案し，metric labelingについてはKleinberg and Tardosと同じ近似比2を得て，その他にもオークションの勝者決定やハブ配置問題に対しても近似を与えることができたという話でした．直観的でわかりやすかったです．

組合せ最適化のセッションでRico Zenklusenが話した「A flow model based on polylinking systems」も面白かったです．Avestimer et al. '07が提案したADTモデルというワイヤレスネットワーク上での情報流のモデルにおいてより多くの信号を送るにはどうしたらよいか，という問題に対して最近Amandruz and Fragouliが多項式時間アルゴリズムを与えました．この研究ではそのマトロイド的な構造を探るためにSchrijverが研究したlinking systemを考察し，linking network，linking flowという概念を提案し，ある種の最大流最小カット定理を証明し，多面体的な側面も考察しています．それによって，より一般的な場合に対する多項式時間アルゴリズムが導かれるという話でした．

混合整数計画法セッションのLeo Liberti「Reformulations in Mathematical Programing: Symmetry」では問題の定式化が持っている対称性を検知するために問題から有向グラフを作り，そのグラフのある種の同型性を判定することで元の問題の持つ対称性が見つかるという話で，見つかった対称性を取り除くように定式化し直すことでベンチマーク問題を今までよりも高速に解くことができる，という報告をしていました．ベンチマーク問題のほとんどに何かしらの対称性が見つかったということで，その観察も興味深かったです．

同じセッションでVolker Kaibelが「Tractable and Intractable Orbitopes」という講演をしました．p×qの01行列全体の中で列集合に作用する群から生じる軌道において辞書順最大のもの全体を集めた集合の凸包をorbitopeと呼ぶことにして，群が対称群のときにorbitopeやそれに関連する多面体がどのように記述できるか，またはできないか，という内容でした．

この日2つ目の招待講演はMartin Skutellaの「Network Flows over Time」でした．いわゆる動的フローの話で，割と慣れている話なので聞きやすく，講演自体も絵が多くてわかりやすかったのでとてもよかったです．最新の研究結果として，多始点1終点のネットワークにおけるearliest arrival flow問題に対する強多項式時間アルゴリズム (Baumann and Skutella 2009)，Earliest arrival flowの避難計画への応用としてのhttp://www.zet-evakuierung.de/，動的フローに対するナッシュ均衡の話 (Koch and Skutella 2009) も紹介されました．