久々に論文でも眺めながら

他にすることがいろいろあるような気がするけども，最近あまり論文を読んでいないと思い，とりあえずInformation Processing Lettersの今年上半期の目次と興味のあるアブストラクトを眺めてみることに．

Simple deterministic wildcard matching

Peter Clifford and Raphael Clifford
Information Processing Letters
Volume 101, Issue 2, 31 January 2007, Pages 53-54
http://dx.doi.org/10.1016/j.ipl.2006.08.002

文字列マッチングでテキストとパターンの両方にワイルドカードを許し，ワイルドカードを高々1つ許容するパターン生起を全部正確にdeterministicに求めるアルゴリズム．テキスト長がn，パターン長がmのときに，計算量は(RAMモデルで) O(nlogm)．FFT (高速フーリエ変換) を用いるというFischer-Paterson以来の手法は踏襲しているが，Cole-Harihanan (STOC 2002) の与えた同じ計算量オーダーのアルゴリズムよりもシンプル．

Bottom-up nearest neighbor search for R-trees

Moon Bae Song, Kwang Jin Park, Ki-Sik Kong and Sang Keun Lee
Information Processing Letters
Volume 101, Issue 2, 31 January 2007, Pages 78-85
http://dx.doi.org/10.1016/j.ipl.2006.08.005

R木を用いてNN探索をするとき，トップダウンにやらずにボトムアップにやるというすごい発想．ボトムアップにやるためにハッシュ表を蓄えておく．それによってIOコストが削減されることを実験的に確認．

An improved exact algorithm for the domatic number problem

Tobias Riege, Joerg Rothe, Holger Spakowski and Masaki Yamamoto
Information Processing Letters
Volume 101, Issue 3, 14 February 2007, Pages 101-106
http://dx.doi.org/10.1016/j.ipl.2006.08.010

与えられたグラフの頂点集合を3つの支配集合に分割できるかどうか答える問題に対してO*(2.695^n)時間アルゴリズムを提案．O*記法は多項式因子を無視．

The hardness of the Expected Decision Depth problem

Dana Ron, Amir Rosenfeld and Salil Vadhan
Information Processing Letters
Volume 101, Issue 3, 14 February 2007, Pages 112-118
http://dx.doi.org/10.1016/j.ipl.2006.08.012

n変数論理関数とn個の変数のオーダリングが与えられているとして，そのオーダリングに従って変数への値の割当を一様ランダムに固定していくとき関数値が定まるまでに値を割り当てられた変数の個数の期待値の計算をする問題が#P困難であることを示している．

Three-coloring planar graphs without short cycles

Min Chen, Andre Raspaud and Weifan Wang
Information Processing Letters
Volume 101, Issue 3, 14 February 2007, Pages 134-138
http://dx.doi.org/10.1016/j.ipl.2006.08.009

平面的グラフは4彩色可能であるけど (いわゆる4色定理)，Groetzschの定理は長さ3の閉路を含まない平面的グラフは3彩色可能であることを示している (実はこの事実は4色定理以前に知られている)．Steinbergは長さ4と5の閉路を含まない平面的グラフが3彩色可能であることを予想したが，それを緩和してErdosは長さ4からkの閉路を含まない平面的グラフが必ず3彩色可能となるような自然数kの存在を予想した．それが正しいことはAbbott-Zhou (1991) によって証明された．彼らはそのようなkが高々11であることを示した．その後，Borodin (1996) とSanders-Zhao (1995) が独立に上界を「高々9」に改善し，Borodin-Glebov-Raspaud-Salavatipour (2005) は「高々7」に改善している．更に，Xu (2006 JCTB) は長さ4,5,7の閉路を含まない平面的グラフが3彩色可能であることを示して，Zhang-Wu (2005) は長さ4,5,6,9の閉路を含まない平面的グラフが3彩色可能であることを示した．この論文は長さ4,6,7,9の閉路を含まない平面的グラフが3彩色可能であることを示している．

The VC dimension of k-fold union

David Eisenstat and Dana Angluin
Information Processing Letters
Volume 101, Issue 5, 16 March 2007, Pages 181-184
http://dx.doi.org/10.1016/j.ipl.2006.10.004

VC次元がdの集合族において，そのメンバk個の合併の族のVC次元がO(dklogk)になるという結果が知られているけども，それがタイトであることをこの論文では示している．確率論的手法．同じことが合併の代わりに共通部分をとる場合でもいえる．d次元空間中のk個の半空間の共通部分からなる集合族のVC次元については未解決問題．

Inapproximability of the kidney exchange problem

Peter Biro and Katarina Cechlarova
Information Processing Letters
Volume 101, Issue 5, 16 March 2007, Pages 199-202
http://dx.doi.org/10.1016/j.ipl.2006.09.012

「腎臓移植問題」と訳してしまうとなんか重い雰囲気を持ってしまうけども，これをゲーム理論の枠組で考えるため「腎臓移植ゲーム」ということばを充ててしまうとこれまた変な雰囲気を感じてしまう．この論文では腎臓移植ゲームのコア配分の中で適当な提供者が見つかる患者の数を最大化するものを見つける問題が大きく近似困難であることを示している．

A linear time algorithm for max-min length triangulation of a convex polygon

Shiyan Hu
Information Processing Letters
Volume 101, Issue 5, 16 March 2007, Pages 203-208
http://dx.doi.org/10.1016/j.ipl.2006.09.014

凸多角形の三角形分割で最短辺長が最大になるものを線形時間で見つけるアルゴリズムの提案．
そのような三角形分割では最短辺が凸包上に来ることがポイントのようだ．

Approximation algorithms for minimizing segments in radiation therapy

Shuang Luan, Jared Saia and Maxwell Young
Information Processing Letters
Volume 101, Issue 6, 31 March 2007, Pages 239-244
http://dx.doi.org/10.1016/j.ipl.2006.10.003

放射線治療の計画に関する論文．これは非負整数行列を特殊な01整数行列の非負整数結合として表わす際に用いる行列の数を最小化する問題として定式化される．その枠組がなかなか面白い．

Scalable Bloom Filters

Paulo Sergio Almeida, Carlos Baquero, Nuno Preguiça and David Hutchison
Information Processing Letters
Volume 101, Issue 6, 31 March 2007, Pages 255-261
http://dx.doi.org/10.1016/j.ipl.2006.10.007

Bloomフィルタは集合のためのデータ構造だけども，false positive (つまり，蓄えられていない要素を蓄えられているものと答えることがある) を許す．しかし，false positiveの確率を予め決めておけばそれに応じてデータ構造を構成できる．確率を高くすればデータ構造の大きさをより小さくできるところに利点がある．中身ではハッシュを使っている．
この論文では，要素数がどんどん増えていってもそれに応じてデータ構造を大きくできる工夫を提案している．
ちなみに「Bloom」は人名．

Five-step FFT algorithm with reduced computational complexity

Rami Al Na'mneh and W. David Pan
Information Processing Letters
Volume 101, Issue 6, 31 March 2007, Pages 262-267
http://dx.doi.org/10.1016/j.ipl.2006.10.009

よくわからないけれども，Takahashiによるfive-step高速フーリエ変換というものがあるそうで，それの算術演算回数とメモリ使用量を削減する話．実験も行なってる．

Greedy online frequency allocation in cellular networks

Joseph Wun-Tat Chan, Francis Y.L. Chin, Deshi Ye, Yong Zhang and Hong Zhu
Information Processing Letters
Volume 102, Issues 2-3, 30 April 2007, Pages 55-61
http://dx.doi.org/10.1016/j.ipl.2006.11.015

ワイヤレスネットワークの周波数割当問題に対するオンラインアルゴリズム．貪欲アルゴリズムの競合比が11/7になることを示している (これはタイト)．

Sweeping simple polygons with the minimum number of chain guards

Xuehou Tan
Information Processing Letters
Volume 102, Issues 2-3, 30 April 2007, Pages 66-71
http://dx.doi.org/10.1016/j.ipl.2006.11.010

k人の警備員で単純多角形の内部をスイープするためのアルゴリズム．そのために必要な最小のkをO(n^2)時間で求め，実際のスイープ計画をO(kn^2)で求める．
Efrat, Guibas, Har-Peled, Lin, Mitchell, Muraliの結果 (SODA 2000) を改善．

Dynamic programming algorithms for the mosaic longest common subsequence problem

Kuo-Si Huang, Chang-Biau Yang, Kuo-Tsung Tseng, Yung-Hsing Peng and Hsing-Yen Ann
Information Processing Letters
Volume 102, Issues 2-3, 30 April 2007, Pages 99-103
http://dx.doi.org/10.1016/j.ipl.2006.11.006

与えられた2つの文字列の最長共通部分文字列を求める問題はよく知られているけども，ここでは1つの文字列Ｔとs個の文字列S1,...,Ss，そして自然数kが与えられたときに，s個の文字列を(重複を許して)k個つなげて (それをCと呼ぶことにして)，TとCの最長共通部分文字列長が最大になるようにするにはどうしたらよいか考えている．この問題に対してO(n^2ms+n^3logk)時間アルゴリズムとO(ns(m+k))時間アルゴリズムを与えている．ただし，nはTの長さ，mはS1からSsの長さの最大値である．もっと速くできてもおかしくない気がするけど，どうなんだろうか．

Powering requires threshold depth 3

Alexander A. Sherstov
Information Processing Letters
Volume 102, Issues 2-3, 30 April 2007, Pages 104-107
http://dx.doi.org/10.1016/j.ipl.2006.11.003

計算量理論のことは全然わかんないけど，なんかすごい．
整数のm乗の計算を深さ2の多数決回路で計算させるなら，そのサイズが2^Ω(n/logn)でないといけない，という話．ただし，nは入力整数のビット長．
Siu-Roychowdhury (1994 SIAMDM) が深さ3なら多項式サイズでできることを示してるので，深さに関してこの結果はタイト．

Dynamic Shannon coding

Travis Gagie
Information Processing Letters
Volume 102, Issues 2-3, 30 April 2007, Pages 113-117
http://dx.doi.org/10.1016/j.ipl.2006.09.015

普通のShannon符号化は2パスで行なわれるのに対して，ここでは1パスでShannon符号化 (のようなもの) を行なう．1パスしか使わないので，文字の出現頻度を予め計算しておくことはできないが，今現在処理しようとしている文字の前の文字までの出現頻度から符号語を計算するようにしている．

Fast and simple algorithms to count the number of vertex covers in an interval graph

Min-Sheng Lin
Information Processing Letters
Volume 102, Issue 4, 16 May 2007, Pages 143-146
http://dx.doi.org/10.1016/j.ipl.2006.12.002

区間グラフの頂点被覆の数と極小頂点被覆の数を線形時間で求めるアルゴリズム．
Okamoto-Uehara-Unoの論文がメインレファレンス (ということだけが個人的にうれしい)．

Multidimensional heaps and complementary range searching

Peter Brass
Information Processing Letters
Volume 102, Issue 4, 16 May 2007, Pages 152-155
http://dx.doi.org/10.1016/j.ipl.2006.12.008

各要素のキーがd次元ベクトルになっているようなデータに対するヒープを考える．サポートする操作は，挿入，削除，与えられた座標の最小発見，与えられた座標の最小除去．シンプルで面白い．これだからデータ構造は面白い．

An in-place algorithm for Klee's measure problem in two dimensions

Jan Vahrenhold
Information Processing Letters
Volume 102, Issue 4, 16 May 2007, Pages 169-174
http://dx.doi.org/10.1016/j.ipl.2006.12.004

2次元平面上に与えられた複数の軸平行長方形 (つまり，各辺がx軸かy軸に平行な長方形) の合併の面積を求める問題に対するin-placeアルゴリズム．時間計算量はO(n^{3/2}logn)，領域計算量はO(1)ワード．

k-Restricted rotation distance between binary trees

Fabrizio Luccio, Antonio Mesa Enriquez and Linda Pagli
Information Processing Letters
Volume 102, Issue 5, 31 May 2007, Pages 175-180
http://dx.doi.org/10.1016/j.ipl.2006.12.007

WADS2005より．
頂点数が同じ2つの根付き二分木は回転操作によって移りあうことができるが，その回転の最小回数が回転距離と呼ばれるものである．回転距離のタイトな上界2n-6のSleator-Tarjan-Thurstonによる証明 (1988 J AMS) では双曲幾何学を使っているところが興味深い．後になってLuccio-Pagli (1989) がもっとシンプルな証明を与えたけども．
そして，回転を根，または根の右側の子供にだけ制限した場合はその距離を制限回転距離と呼ぶ．Cleary-Taback (IPL 2003) は群をつかってタイトな上界4n-8を証明した．ここでは，それ (を精緻化したもの) のシンプルな証明を与える．
次に，回転を根からのレベルがkまでの頂点にだけ制限した場合の距離をk制限回転距離と呼ぶことにして，k=2の場合 (つまり，根と根の子供だけで回転可能な場合) に4n-6という上界を示している．下界は4n-12のようだ．kが2よりも大きい場合はほとんど何もわかってないみたい．

ちなみに，タイトルを数学記号で始めるのはあまりよろしくない．

Lower bounds for testing Euclidean Minimum Spanning Trees

Oren Ben-Zwi, Oded Lachish and Ilan Newman
Information Processing Letters
Volume 102, Issue 6, 15 June 2007, Pages 219-225
http://dx.doi.org/10.1016/j.ipl.2006.12.011

平面上の点集合とその上の幾何グラフが与えられたとき，それが最小全域木であるかどうか判定する問題について．いわゆるproperty testingの論文で，εテスタのquery complexityの下界を与えている．使っている手法はいわゆるYaoの原理で，乱択アルゴリズムの最悪計算量をdeterministicアルゴリズムの平均計算量で下から評価するというもの．Non-adaptiveな場合はCzumaj-Sohler-Ziegler (ESA 2000, TALG to appear) の与えたεテスタのquery complexityとほとんど合致．

The cycle roommates problem: a hard case of kidney exchange

Robert W. Irving
Information Processing Letters
Volume 103, Issue 1, 30 June 2007, Pages 1-4
http://dx.doi.org/10.1016/j.ipl.2007.02.003

また臓器移植問題．安定なマッチングが存在するかどうかを判定する問題がNP完全という結果．

On Chen and Chen's new tree inclusion algorithm

Hai-Lung Cheng and Biing-Feng Wang
Information Processing Letters
Volume 103, Issue 1, 30 June 2007, Pages 14-18
http://dx.doi.org/10.1016/j.ipl.2007.02.006

Chen-Chen (IPL 2006) の提案したtree inclusion問題に対するアルゴリズムの解析が間違ってるよ，ということを指摘する論文．
ちなみに，このChen-Chenの2人のChenとこの論文の著者であるChenは別人のようだ．

Approximately n-secting an angle

Seok Woo Kim, Seong-Hun Paeng and Hee Je Cho
Information Processing Letters
Volume 103, Issue 1, 30 June 2007, Pages 19-23
http://dx.doi.org/10.1016/j.ipl.2007.02.007

定規とコンパスだけで角の三等分ができないことは今となってはよく知られた事実だけども，この論文では定規とコンパスだけで角のn等分の近似を求める方法を提案している．