引き続きIPL
Information Processing Lettersの今年7月から9月までを見ていきます．
Average-case analysis of QuickSort and Binary Insertion Tree height using incompressibility
Brendan Lucier, Tao Jiang and Ming Li
Information Processing Letters
Volume 103, Issue 2, 16 July 2007, Pages 45-51
http://dx.doi.org/10.1016/j.ipl.2007.01.007
Kolmogorov complexityによる非圧縮可能性法 (incompressibility method) を用いてアルゴリズムの平均値解析を行なう手法があるようで (これ自体を知らなかったので勉強になった)，その手法によってQuickSortを解析するという話．
Approximating geodesic tree distance
Nina Amenta, Matthew Godwin, Nicolay Postarnakevich and Katherine St. John
Information Processing Letters
Volume 103, Issue 2, 16 July 2007, Pages 61-65
http://dx.doi.org/10.1016/j.ipl.2007.02.008
Billera-Holmes-Vogtmann (Adv Appl Math 2001) が考察した系統樹の空間における距離をここではgeodesic tree distanceと呼ぶことにして，それが√2近似可能であることを示している．
Linear structure of bipartite permutation graphs and the longest path problem
Ryuhei Uehara and Gabriel Valiente
Information Processing Letters
Volume 103, Issue 2, 16 July 2007, Pages 71-77
http://dx.doi.org/10.1016/j.ipl.2007.02.010
二部置換グラフ (bipartite permutation graph) に対して綺麗な分解定理を示して，その分解を線形時間で求めるアルゴリズムを提案．それを利用して二部置換グラフの最長路問題を線形時間で解いている．
Robustness of PSPACE-complete sets
A. Pavan and Fengming Wang
Information Processing Letters
Volume 103, Issue 3, 31 July 2007, Pages 102-104
http://dx.doi.org/10.1016/j.ipl.2007.02.018
計算量理論はよく分からないんだけども，PSPACE完全な言語がP-selective sparse集合に対してロバストであることを証明している．同様な結果はEXPとNPに対しては知られていたようだ．
ちなみに，C完全な言語Lが集合Sに対してロバストであるとは，L-SがC完全 (またはC困難) であることと定義する．
All NP-problems can be solved in polynomial time by accepting hybrid networks of evolutionary processors of constant size
Florin Manea and Victor Mitrana
Information Processing Letters
Volume 103, Issue 3, 31 July 2007, Pages 112-118
http://dx.doi.org/10.1016/j.ipl.2007.03.001
またよく分からない話題だけども，accepting hybrid networks of evolutionary processors (AHNEP) という計算モデルがあるようで，大きさ24のAHNEPを使えばNPの問題が多項式時間で解ける，という話．
Discriminative learning can succeed where generative learning fails
Philip M. Long, Rocco A. Servedio and Hans Ulrich Simon
Information Processing Letters
Volume 103, Issue 4, 16 August 2007, Pages 131-135
http://dx.doi.org/10.1016/j.ipl.2007.03.004
COLT2006より．
Generative learningでは学習できないがDiscriminative learningでは学習できる例が存在することを示す，という内容．学習アルゴリズムのモデルとしてprobably approximately bayesというものを考えている．
A logical approach to multicut problems
Georg Gottlob and Stephanie Tien Lee
Information Processing Letters
Volume 103, Issue 4, 16 August 2007, Pages 136-141
http://dx.doi.org/10.1016/j.ipl.2007.03.005
Multicut問題は木幅が定数でもNP困難なのだけども，ここでは付随するstructureの木幅を考えて，それをパラメータとしてみた場合はFPT (fixed parameter tractable) になることを示している．いわゆるmonadic second order logic (MSOL) による論法．
On 3-colorable planar graphs without cycles of four lengths
Xiaofang Luo, Min Chen and Weifan Wang
Information Processing Letters
Volume 103, Issue 4, 16 August 2007, Pages 150-156
http://dx.doi.org/10.1016/j.ipl.2007.03.007
似たような論文を昨日みたような気がしたけど，実は著者が3人中2人同じだった．
長さ4,6,7,8の閉路を持たない平面的グラフが3彩色可能であることを示している．
On the fixed-parameter tractability of the equivalence test of monotone normal forms
Matthias Hagen
Information Processing Letters
Volume 103, Issue 4, 16 August 2007, Pages 163-167
http://dx.doi.org/10.1016/j.ipl.2007.03.009
与えられた単調DNF式と単調CNF式の等価性判定問題 (これはハイパーグラフ極小横断列挙と多項式時間等価) に対する固定パラメータアルゴリズムを提案．パラメータとしては変数の数，DNF式の方の単項式の数，DNF式の方での各変数を含まない単項式の数の (変数に関する) 最大値を考えている．
Primal-dual approximation algorithms for the Prize-Collecting Steiner Tree Problem
Paulo Feofiloff, Cristina G. Fernandes, Carlos E. Ferreira and José Coelho de Pina
Information Processing Letters
Volume 103, Issue 5, 31 August 2007, Pages 195-202
http://dx.doi.org/10.1016/j.ipl.2007.03.012
賞金収集Steiner木問題に対して，主双対法に基づく近似アルゴリズムを提案．Goemans-Williamson (SIAM Comp 1995) では主双対法によるO(n^3 logn)時間の2-1/(n-1)近似アルゴリズムが提案されていたが，それを改善してO(n^2 logn)時間の2-2/n近似アルゴリズムを示している．
A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs
Shin-ichi Nakayama and Shigeru Masuyama
Information Processing Letters
Volume 103, Issue 6, 15 September 2007, Pages 216-221
http://dx.doi.org/10.1016/j.ipl.2007.03.014
グラフの辺ランキングとは，辺の番号付けで，同じ番号を持つ任意の2辺に対してそれらを結ぶ任意のパス上に番号が大きな辺が存在するようなもののことである．辺の番号の最大値を最小にする問題が最小辺ランキング問題である．一般のグラフに対してこれはNP困難である (Lam-Yue DAM 1998) が，多項式時間で解けるグラフのクラスとして木が知られている．この論文では外平面的グラフに対する多項式時間アルゴリズムを提案している．
A linear-time algorithm for computing the multinomial stochastic complexity
Petri Kontkanen and Petri Myllymaki
Information Processing Letters
Volume 103, Issue 6, 15 September 2007, Pages 227-233
http://dx.doi.org/10.1016/j.ipl.2007.04.003
統計的モデル選択に現れるMDL (minimum description length) 原理はnormalized maximum likelihood分布から得られる標本のcodelength (これをstochastic complexityと呼んでいるようだ) に基づいているようで，考えるモデルクラスが多項モデル (multinomial model) の場合にそのstochastic complexityを線形時間で計算するアルゴリズムを与えている．
Efficient algorithms for regular expression constrained sequence alignment
Yun-Sheng Chung, Chin Lung Lu and Chuan Yi Tang
Information Processing Letters
Volume 103, Issue 6, 15 September 2007, Pages 240-246
http://dx.doi.org/10.1016/j.ipl.2007.04.007
2つの文字列のアラインメントで，与えられた正規表現にマッチする部分を同じ箇所に含むようなものを求める問題をArslan (CPM 2005) は考えた．ここでは，その問題に対してより高速なアルゴリズムを提案している．
Dicing on the Streett
Florian Horn
Information Processing Letters
Volume 104, Issue 1, 30 September 2007, Pages 1-9
http://dx.doi.org/10.1016/j.ipl.2007.04.010
分散システムに明るくないので，内容もよく分からないけど，なんか面白そうなのでとりあえず記録だけ．
雰囲気はmean payoff gameに似てる気がする．
A note on the Hadwiger number of circular arc graphs
N.S. Narayanaswamy, N. Belkale, L.S. Chandran and N. Sivadasan
Information Processing Letters
Volume 104, Issue 1, 30 September 2007, Pages 10-13
http://dx.doi.org/10.1016/j.ipl.2007.04.008
Circular-arcグラフに対して，最大クリークマイナーの大きさ (つまり，グラフがK_rをマイナーとして含むようなrの最大値) が染色数の2倍-1で上から抑えられることを示している．
The finite horizon investor problem with a budget constraint
Asaf Levin
Information Processing Letters
Volume 104, Issue 1, 30 September 2007, Pages 21-28
http://dx.doi.org/10.1016/j.ipl.2007.05.001
はじめにいくらか資金を持っていて，多期間に渡って投資をする．各期に支払う費用は決まっていて，得られる利益は非負確率変数である．この確率変数がどんなものかも分かっているとする．投資を一旦やめたらその後に投資を続けられない．この状況で最終的な持ち金の期待値を最大にする投資戦略を求める問題を考える．この論文ではこれがNP困難であることを示し，完全多項式時間近似スキーム (fully polynomial-time approximation scheme, FPTAS) を提案している．
