ISAAC 2009
今まで書いてきたように先週ISAAC (International Symposium on Algorithms and Computation) に行ってきたわけですが，勉強になった内容や面白かったものについて書いていきます．パラレルセッションのため聞けなかった話については残念ながら割愛します．
その前に，全体的な印象ですが，論文数がやたら多かった割にはレベルが低くなかった気がします．
http://www.informatik.uni-trier.de/~ley/db/conf/isaac/isaac2009.html
(このリストには漏れがたくさんあります．)
Ronald L. Graham: Bubblesort and Juggling Sequences
Grahamの招待講演．基本的には次のarxiv論文の内容とその続きの話．
http://arxiv.org/abs/0908.2456
ジャグリング数列というものが世の中にはあって，ここでいうジャグリングはお手玉とかのジャグリングです．それとバブルソートをつなげる概念が置換の「maxdrop」というもの．このmaxdropはいままであまり研究がされてきてなかったので，それを詳しくやってみたら面白いものが出てきた，というような話．
要素数nの集合上の置換でmaxdropがk以下，下降列の数がrのものを数え上げることで，母関数を作ってみる．その式をじーっと見てると対称性があるような，ないような，よく分からない格好をしている．それを徹底的に解剖して，母関数のclosed formulaを導きだす．ふむ．数え上げ組合せ論の王道だ．これがだいたい上のarxiv論文の話．
しかし，ここで終わらない．このdropの概念を半順序集合に拡張し，同じように母関数を作ってみる．そうすると，(二項係数を基底として多項式を書いたときの) 係数がもとの半順序集合のcocomparability graphの染色多項式になっているということが証明できる．ちょっと感動．そうすると，もっと一般のグラフにまで拡張したくなるけど，それについてはまだできていないみたい．思わぬところでグラフとつながってきて，そこが未解決だといわれるから面白い．
Francisco Claude, Reza Dorrigiv, Stephane Durocher, Robert Fraser, Alejandro López-Ortiz, Alejandro Salinger: Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm
http://dx.doi.org/10.1007/978-3-642-10631-6_7
平面上にn個の点とm個の単位円板があるとき，その単位円板をいくつか選んで点を全部被覆したい．選ぶ円板の数を最小化する，という問題．
これはNP困難だけど，近似アルゴリズムがいろいろと作られてきた．しかし，その近似比は2004年に108，2006年に72，2007年に38だった．ようやく今年になって多項式時間ε近似 (PTAS) ができると分かったが，計算量が無茶苦茶大きい (2近似を達成しようとすると計算量がO(m^{257} n))．
ということで，この論文は22近似だけど計算量がO(m^2 n^4)のものを提案．
主な貢献は．中でサブルーチンとして使っている問題がgreedyアルゴリズムで最適に解けるというところが面白い．
Imran A. Pirwani: Shifting Strategy for Geometric Graphs without Geometry
http://dx.doi.org/10.1007/978-3-642-10631-6_38
平面上のunit disk graphの最大独立集合問題に対するPTASは今となってはスタンダードになったshifting strategyによって可能となったが，それを実行するためにはグラフが平面上のunit diskとして幾何的に実現されていなくてはならなかった．しかし，Niebergらは幾何的な実現がなくてもグラフだけからPTASが作れることを示し，これはすごかった．(私も2004年のWGでT. Niebergの話を聞いて感動した．)
さて，一方unitとは限らないdisk graphの最大独立集合問題に対するPTASはshifting strategy+dynamic programmingで実現できる (Erlebachら SODA '01)．しかし，幾何的な実現がなくてもPTASが作れるかどうかは分かっていなかった．この論文では，各頂点に対応するdiskの半径と，辺に対応する2つのdiskの中心間距離が全部分かっているときには幾何実現がなくてもPTASが作れるという結果を与えている．センサネットワークの気持ちでいうと，位置同定をしなくても，各センサのradio rangeと通信できてるセンサ間の距離が分かっていれば問題のε近似が多項式時間で得られる，というようなことになる．
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Daniel Meister, Saket Saurabh: Bandwidth on AT-Free Graphs
http://dx.doi.org/10.1007/978-3-642-10631-6_59
グラフのバンド幅問題といえば，難しい問題の典型例で，入力グラフが木の場合であってもparameterized complexityの観点からも難しい (最大独立集合や最小支配集合よりも難しい)．
入力グラフがAT-freeであっても問題はNP困難のままだけども，parameterized complexityの観点から，この論文では固定パラメータ・アルゴリズムを与えている．
Xi Chen, Shang-Hua Teng: Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria
http://dx.doi.org/10.1007/978-3-642-10631-6_66
Best paper．話は聞いてないけど．
Paul S. Bonsma, Felix Breuer: Finding Fullerene Patches in Polynomial Time
http://dx.doi.org/10.1007/978-3-642-10631-6_76
グラフ理論的に言うと，フラーレンとは平面的3正則グラフで，各面が五角形か六角形であるもののこと．この論文の結果よりも，最後のDiscussionのところにある未解決問題や予想が気になる．
Siddhartha Sen, Robert Endre Tarjan: Deletion without Rebalancing in Multiway Search Trees
http://dx.doi.org/10.1007/978-3-642-10631-6_84
探索木というデータ構造は厄介で，探索や挿入という操作に比べて削除が異様にややこしい．木の高さをうまく調整するためにrebalancingを行うのだけど，その記述も大変だし，解析もややこしい．ということで，実際にはあまりrebalancingは行われていないらしい (この発表によると)．
ということで，この論文ではrebalancingしないB木もどきを提案し，それに対する各操作の計算量解析を与えている．
来年1月のSODAでは二分木に対して同じようなことをやるらしく，そっちの方がテクニカルには難しいらしい．
Therese C. Biedl, Stephane Durocher, Jack Snoeyink: Reconstructing Polygons from Scanner Data
http://dx.doi.org/10.1007/978-3-642-10631-6_87
単純多角形が与えられてその中にいくつかレンジ・スキャナがある．そのスキャナから得られるデータから元の単純多角形が復元できるかどうかという問題の考察．レンジ・スキャナがどのようなデータを収集するかによっていろんなモデルが考えられ，また，与えられる単純多角形のクラスによっても異なる問題が得られる．結果は大まかにいって，一般の単純多角形に対してはほとんどのモデルで問題がNP困難になり，単調多角形や星型多角形の場合，あるモデルでは多項式時間で解ける，というもの．
Sylvain Guillemot, Stéphane Vialette: Pattern Matching for 321-Avoiding Permutations
http://dx.doi.org/10.1007/978-3-642-10631-6_107
置換Pの中に短い置換Qが含まれるということを，Qの順序を守るsubsequenceがPに含まれることとする．例えば，P=3215674で，Q=132のとき，PはQを含む．というのは，Pのsubsequenceである154の数字の順番がQと同じだから．
Pの長さがnで，Qの長さがkのとき，PがQを含むかどうかの判定はO(n^k)時間でできる．しかし，一般にこの問題はNP完全である．
この論文ではQが特定のパターンを含まない場合を考える．Qが132, 312, 213, 231のいずれかを含まない場合は既存研究から多項式時間で解けることが分かっている．なので，残された場合は123と321である．これらは互いに逆順なので，ここでは321にのみ焦点を当てる．
結果は次の通り，PもQも321を含まないときは多項式時間で解ける (ただし，論文に書いてあるアルゴリズムはProposition 3が正しくないため間違っている．発表では修正版を紹介していて，これはジャーナル版に掲載される予定)．Qのみが321を含まないときはO(kn^{4\sqrt{k}+12})時間で解ける．
