No Such Blog or Diary

«Prev || 1 | 2 | 3 |...| 11 | 12 | 13 || Next»

SDPの効率化?

ちゃんと資料を追わなかったので分からんのだけど,元の式の対称性を使って変数を減らしたときに正定値条件は必要十分でカバーできるけど目的関数の最適性って保存されるのだろうか? 変数を減らすプロセスに目的関数の係数行列ってでてきてたっけ? 気になってきたのでそのうち確認しよう.

考え中

昨日のシフトアルゴリズムの証明を追い終えた.木の重さが単調に増えるという条件を多少緩められるといいのだけど… 「最大の重さを持つ木」に関する性質がアルゴリズムの中心にあるのでこの点の改良は結構大変そう.ポテンシャル突っ込んだら終了とかいう簡単な解決が出来ると楽なんだけど.

訪問二日目

Tree Partitioning の話が出る:「木のノードに非負の重みがつけられている.木から k-1 本の片を取り除いて k 個の木に分割する.分割された木の重さを,それに含まれるノードの重みの和とする.このとき,分割された木の重さの最大を最小にする分割を求めよ.」

最後の部分は最小を最大にするとか,最小ないし最大を制限するとかの派生がある.んで,この問題自体は多項式ないし線形オーダーのアルゴリズムがあるらしい.多項式のやつに関してはセパレータを適当にシフトしてくだけでよいらしい.max-min は簡単なシフトのみ, min-max は二種類のシフトを使うとのこと.証明追ってるけどシフトのみでいけるってのは面白いなぁ.

研究室訪問

ENS Lyon にある研究室を訪問.とりあえず自分の研究を発表.一応これにて今回の旅の自分の仕事は終了.あとは共同研究のお話を聞く.んで,夕食はレストランでご馳走になる.とりあえず生の馬肉を食らう.刺身でなくハンバーグの焼く前のような状態.面白い味ではあったのだが量が多すぎて後半味がしない.やっぱりこっちの料理は量が多すぎる.消化は問題ないけどしばらく飯イラネ.

三日目

発表終わった.ふたつほど質問がうまく聞き取れなかった… というか,想像範囲外からの質問は英語がうまく聞き取れん.話し手が親切だと聞き取りやすい英語を話してくれるので楽なのだが.なにはともあれ仕事も半分終了.明日はLyonへ.

二日目

テクニカルセッション後に Mont-Saint-Michel へのエクスカーションとバンケット.とりあえず世界遺産らしい.昔は海に囲まれた島だったらしいけど今は砂が堆積してしまってて砂に囲まれた島で… なにやら土砂をどけたり道を壊して橋をかけるとかの計画があるらしい.まあ,地球温暖化で海面上昇すれば問題ない気もする.

«Prev || 1 | 2 | 3 |...| 11 | 12 | 13 || Next»
Search
Feeds

Page Top