2012-02-06
■[論文紹介] A Constructive Proof of the Cycle Double Cover Conjecture 
Alexander Souza
http://arxiv.org/abs/1202.0569
タイトルを見て2つ驚いた．1つはCycle Double Cover Conjectureが解けたこと．もう1つはconstructiveであるということ．実はこんなタイトルがついているので，non-constructiveな証明が既に知られていたのか，と焦ったのだけど，そうでもないようで，この論文がCycle Double Cover Conjectureに対する最初の証明を与えているようだ．
Cycle Double Cover Conjectureといえばグラフ理論の大きな未解決問題だったもので，カット辺のない3正則グラフには必ず各辺を2回ずつ使うような6つの完全マッチングが存在する，という有名な予想．3正則グラフのTSPのLP緩和と関係のある話．昔，私の授業でも未解決問題として紹介したことがある (PDFなので注意)．
2012-01-27
■Ernst Specker 
FortnowとGaraschのブログより．Ernst Speckerが亡くなったというニュース．御冥福をお祈りします．
私がチューリヒにいた頃，既にSpeckerは退職していたけど，セミナーやコロキウムにはたまに出てきたりしていた．杖をつきながらではあったが，歩くことには全く問題はなく，元気そうだったことを鮮明に覚えている．私になじみのあるSpeckerの結果はpartial satisfactionに関するLieberherrとSpeckerの論文である．MAX SATの近似アルゴリズムを語るときによく出てくる論文で，その話題のはしりとなったものといってもいいかもしれない．
■[論文紹介] SODA 2012から 
もうそろそろ書かないと，書く機会を失ってしまいそうなので，何とか書きます．
聞いてない話もありますし，聞いた話でも勘違いがあるかもしれないのは，いつも通りとします．
Computing all maps into a sphere
Martin Čadek, Marek Krčál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek and Uli Wagner
Best paperの論文．泣く泣く聞きにいかなかったけど．
2つの位相空間X, Yが (単体的複体として) 与えられたとき，XからYへの連続写像を全部計算するというアルゴリズムを提案．ただし，Yはd次元球面で，Xの次元は2d-2以下であるとする．この条件が満たされているとき，XからYへの連続写像全体は有限生成アーベル群となるそうで，その生成元を列挙するということが上で言った「連続写像を全部計算する」という意味．こういうのはいわゆる「数学に対する計算世界観」であって，とても面白そうではある．
Dimension reduction for finite trees in l_1
James Lee, Arnaud De Mesmay and Mohammad Moharrami
これも泣く泣く聞かなかった話し．
Jonhson-Lindenstraussの補題はl_1に対して成り立たないので，成り立たせようとするならば考える距離空間を制限しないといけない．ここでは木に制限．頂点数nの木は，歪みがなければn-1次元に埋め込めるが，歪みを許したらどうなるか？この論文では歪みを任意の定数としてO(log n)次元に埋め込めることを示している．
Kernelization of Packing Problems
Holger Dell and Dániel Marx
カーネル化のセッションから．集合充填問題に対するカーネルはsunflower補題が与えるものが (オーダーの意味で) 最適，という話．グラフHを固定して，与えられたグラフGに頂点素なHを充填する問題についてもカーネルを考える．これについてカーネルの大きさの上界はO(k^{|V(H)|})だけど，下界はΩ(k^2)．Holger Dellの話はいつ聞いてもうまいし，スライドもきれい．
Linear Kernels for (Connected) Dominating Set on H-minor-free graphs
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh and Dimitrios Thilikos
H-minor-freeグラフに対する支配集合問題のカーネルで，線形サイズのものを提案．やっぱり木分解とグリッドが重要な役割を果たす．
Packing anchored rectangles
Adrian Dumitrescu and Csaba Toth
単位面積の正方形の中に有限個の点がばらまかれている．ただし，左下角にも1つ点が置かれているとする．このとき，ばらまかれた点を左下隅に持ち，他の点を内部に含まない長方形を使って，できるだけ広い面積を覆うことを考える．ただし，長方形は互いに重なってはいけないとする．ある予想があって，それは「これにより単位正方形の半分以上の面積を必ず覆うことができる」というものである．この論文では必ず9%は覆えるということを証明している．
Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
Haim Kaplan, Shay Mozes, Yahav Nussbaum and Micha Sharir
与えられたモンジュ行列に前処理を施して，クエリとして与えられた小行列の中の最大値を高速に計算するにはどうしたらよいか？という話．モンジュ性から擬直線アレンジメントが自然に得られて，それにより，計算幾何の手法が使えるようになる．面白い．
The Entropy Rounding Method in Approximation Algorithms
Thomas Rothvoss
どうも最近エントロピーが流行っているようで，エントロピーを使って丸めをしようという話．こういうのを聞いてさくさく分かるようにならないといけない．
Approximating CSPs with Global Cardinality Constraints Using SDP Hierarchies
Prasad Raghavendra and Ning Tan
CSPの話をするとややこしいので，MAX BISECTIONで話を進めると，この論文ではMAX BISECTIONの近似アルゴリズムで近似比が0.85のものを得ている．これまでで一番よい近似比は0.7027だった．手法はラサール緩和だけど，エントロピー (!) を使ったα-independenceという概念を持ち出して，それを使うとうまく丸めることができる，という流れ．エントロピーが流行っている．
Linear Index Coding via Semidefinite Programming
Eden Chlamtac and Ishay Haviv
グラフで与えれるside informationがある状況での符号の話で，符号語の長さの最小化を考えている．その長さはグラフの構造に依存するが，ちょうど，安定数とクリーク被覆数の間に入ってくる．こうなると，染色数との関連から，染色数のようなアルゴリズムを考えたくなって，この論文ではそれを実際に考えている．
2012-01-23
■SODA 2012 まだまとめない 
ちょっと疲れてるので，まとめは持ち越し．面白かった話はいろいろあったけど，あとで書く．ここでは，その他軽く書けることだけ．
長いビジネスミーティング．3年に1回は北米以外で開催？来年はマイアミでもマイアミビーチでもなく，ニューオリンズ．再来年はホノルル？ALENEXやANALCOとの関係はどうする？PCの負担に関する長い議論．結論は出ず．SODAを1年に2回やるっていう案は解決にならない気が．
参加者は，(onsite registrationを除くと) アジア，北米，ヨーロッパがそれぞれ約1/3ずつを占める．ホテルでオーガナイズするのは大変そう．おつかれさまでした．しかし，さすが高級ホテルと思わせるところは多々ある．コーヒーブレイクにクロワッサンがほしいと思ってしまう私はヨーロッパかぶれだろうか？
