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がある状況での符号の話で，符号語の長さの最小化を考えている．その長さはグラフの構造に依存するが，ちょうど，安定数とクリーク被覆数の間に入ってくる．こうなると，染色数との関連から，染色数のようなアルゴリズムを考えたくなって，この論文ではそれを実際に考えている．