みたびIPL
Information Processing Letters，今年の10月から12月まで．
An improved upper bound on the queuenumber of the hypercube
Toru Hasunuma and Misa Hirota
Information Processing Letters
Volume 104, Issue 2, 16 October 2007, Pages 41-44
http://dx.doi.org/10.1016/j.ipl.2007.05.006
グラフのk-queueレイアウトとは，頂点を一直線上に並べ，各辺をk個のキューのいずれかに配置して，同じキューにあるどの2辺も入れ子構造を作らないようにしたものである．グラフGのk-queueレイアウトが存在する最小のkをGのqueuenumberと呼ぶ．ここでは，Gがd次元超立方体のとき，Gのqueuenumberがd-2以下になることを示している (ただしdは5以上)．
Scheduling imprecise computation tasks on uniform processors
Guohua Wan, Joseph Y.-T. Leung and Michael L. Pinedo
Information Processing Letters
Volume 104, Issue 2, 16 October 2007, Pages 45-52
http://dx.doi.org/10.1016/j.ipl.2007.05.004
スケジューリングについて．各ジョブにはrelease dateとdeadlineがついている．各ジョブのprocessing timeには必ず処理しなくてはならないmandatoryの時間と処理しなくてもよいoptionalの時間があり，optionalの時間は処理しなくてもいい代わりに処理しない場合にはコストを払わないといけない．コストは処理しなかった時間に各ジョブ固有の重みをかけたものである．機械の状況は一様多機械で処理は割込みなしで行なわれるとする （先行研究では1機械の場合なども扱われているようだ)．扱う目的関数は3つ考えていて，最大コストの最小化，2つ重み関数があって片方のコスト和を最小にする中でもう一方の最大コストの最小化，2つ重み関数があって片方の最大コストを最小にする中でもう一方のコスト和の最小化．どの場合に対しても多項式時間アルゴリズムを与えている．
A 2^{O(k)}poly(n) algorithm for the parameterized Convex Recoloring problem
Igor Razgon
Information Processing Letters
Volume 104, Issue 2, 16 October 2007, Pages 53-58
http://dx.doi.org/10.1016/j.ipl.2007.05.007
木の頂点彩色 (properとは限らない) が凸であるとは，同じ色の頂点集合が連結部分グラフを誘導することである．木の頂点彩色1つ (P) と部分彩色1つ (D) が与えられたときに，Pに従って塗られた頂点をDに従って塗り替えることにより凸彩色が得られるかどうかを考え，その際に塗り替える頂点数kを最小にしたい．Moran-Snir (WADS 2005) はこのkをパラメータとしたときにO(k(k/log k)^k×poly(n))時間アルゴリズムを提案した．この論文ではO(256^k×poly(n))のアルゴリズムを提案している．
On planar path transformation
Selim G. Akl, Md. Kamrul Islam and Henk Meijer
Information Processing Letters
Volume 104, Issue 2, 16 October 2007, Pages 59-64
http://dx.doi.org/10.1016/j.ipl.2007.05.009
平面上の点集合のハミルトンパスについて，点集合が凸の位置にあるとき，任意の2つのハミルトンパスが高々2n-5回のフリップ操作で移りあえることを証明している (ただし，nは点集合のサイズ)．点集合が一般の位置にあるときは任意の2つのハミルトンパスがフリップ操作だけで移りあえるかどうかは不明のようだが，nが8以下の場合については計算機を使って正しいことを示している．点集合が一般の位置になくてもこれが正しいことを予想している．
Improved fixed parameter tractable algorithms for two “edge” problems: MAXCUT and MAXDAG
Venkatesh Raman and Saket Saurabh
Information Processing Letters
Volume 104, Issue 2, 16 October 2007, Pages 65-72
http://dx.doi.org/10.1016/j.ipl.2007.05.014
与えられたグラフの頂点集合を2分割してできるだけ分割クラスの間に横たわる辺の数を多くする問題が最大カット問題 (MAXCUT) で，与えられた有向グラフからできるだけ多くの辺を残すように辺を除去して閉路をなくす問題が最大非閉路部分グラフ問題 (MAXDAG) である．これらの問題に対して先行研究よりも高速なアルゴリズムを提案している．
Parameterized complexity of the induced subgraph problem in directed graphs
Venkatesh Raman and Somnath Sikdar
Information Processing Letters
Volume 104, Issue 3, 31 October 2007, Pages 79-85
http://dx.doi.org/10.1016/j.ipl.2007.05.005
有向グラフDと有向グラフの遺伝的性質P，そして整数kが与えられたときに，DにPを有する頂点数kの誘導部分グラフが存在するかどうかという問題を考える．これがkに関してFPTになる場合とW[1]困難になる場合を特徴付けている (いわゆるdichotomy theorem)．定理の内容はPが (1) すべての独立集合，すべてのcomplete symmetric digraphとすべてのacyclic tournamentを含む，(2) ある独立集合もあるcomplete symmetric digraphもあるacyclic tournamentも含まない，の2条件のいずれかを満たす場合，この問題はFPTであり，そうでなければW[1]困難，というもの．Ramseyの定理を使う論法．同様な結果が無向グラフに対してはKhot-Raman (TCS 2002) によって知られていた (このKhotはunique game conjectureのKhotである)．
On the lexicographical generation of compressed codes
Markus E. Nebel
Information Processing Letters
Volume 104, Issue 3, 31 October 2007, Pages 95-100
http://dx.doi.org/10.1016/j.ipl.2007.05.011
列挙の論文．簡単な組合せ的objectを列挙する手法として，出力対象をうまく正規言語として表わして，そのwordを1つずつ出力していくというものがある．これはある木を走査することに対応し，その走査に関わる時間が全体の計算量となる．計算量を減らすためにトライやパトリシア木のような圧縮を施すことを考えて，それによって実際にどれだけ計算量が減るのかを理論的に評価している．
Optimal per-edge processing times in the semi-streaming model
Mariano Zelke
Information Processing Letters
Volume 104, Issue 3, 31 October 2007, Pages 106-112
http://dx.doi.org/10.1016/j.ipl.2007.06.004
ストリーミングアルゴリズムの論文．グラフ．
頂点数がnのグラフの辺が次々にやってくるけども，O(n polylog(n))ビットしか蓄えられないような計算モデル．このとき，各辺に対してO(1)時間の処理でグラフの連結性，2彩色可能性，k点連結性，k辺連結性，最小費用全域木を求めるアルゴリズムを与えている．
Spanning trees with minimum weighted degrees
Mohammad Ghodsi, Hamid Mahini, Kian Mirjalali, Shayan Oveis Gharan, Amin S. Sayedi R. and Morteza Zadimoghaddam
Information Processing Letters
Volume 104, Issue 3, 31 October 2007, Pages 113-116
http://dx.doi.org/10.1016/j.ipl.2007.06.011
三角不等式を満たす重み付きグラフが与えられたときに，その全域木で各頂点に接続する辺の重み和の最大値を最小にするようなものを求めたい，という問題を考察．これに対して多項式時間4.5近似アルゴリズムを設計し，同時に2近似よりよい多項式時間アルゴリズムが適当な仮定のもとで存在しないことを示している．
Convergence analysis of a self-adaptive multi-objective evolutionary algorithm based on grids
Yuren Zhou and Jun He
Information Processing Letters
Volume 104, Issue 4, 15 November 2007, Pages 117-122
http://dx.doi.org/10.1016/j.ipl.2007.05.013
進化的多目的最適化アルゴリズムの理論的解析．自己適応型(μ+1)アルゴリズムというものがあるようで，あるマイルドな仮定のもとでその出力がほとんど確かにパレート最適解に収束すること，および，パレート最適解に確率収束することを示している．
Uniform metrical task systems with a limited number of states
Wolfgang Bein, Lawrence L. Larmore and John Noga
Information Processing Letters
Volume 104, Issue 4, 15 November 2007, Pages 123-128
http://dx.doi.org/10.1016/j.ipl.2007.06.001
オンラインアルゴリズムの論文．Metrical task systemで，metricがuniform (つまり異なる任意の2点間の距離が1) の場合の話．点の数が小さい場合に既存の最善乱択アルゴリズム (Irani-Seiden TCS 1998) よりもよい競合比の乱択アルゴリズムを提案している．
On constructing an optimal consensus clustering from multiple clusterings
Piotr Berman, Bhaskar DasGupta, Ming-Yang Kao and Jie Wang
Information Processing Letters
Volume 104, Issue 4, 15 November 2007, Pages 137-145
http://dx.doi.org/10.1016/j.ipl.2007.06.008
1つの有限集合の分割がいくつか (k個) 与えられているとき，それらの類似性を測る尺度を提案して，それを計算する問題を考えている．提案された問題はkが2の場合には多項式時間で解けるが，kが3以上の場合にはMAX-SNP困難となり，その場合に2-2/k近似多項式時間アルゴリズムも与えている．
直接関係ないが，類似性の尺度の提案とそれを計算する問題をしっかりと分離することは重要である．それができていないために何をしたいのか分からない研究が世の中にはよくある．
A sufficient condition for a planar graph to be 3-choosable
Liang Shen and Yingqian Wang
Information Processing Letters
Volume 104, Issue 4, 15 November 2007, Pages 146-151
http://dx.doi.org/10.1016/j.ipl.2007.06.005
昨日，おとといとまた似た論文だけども，著者は違うか．
長さ4,6,8,9の閉路を持たない平面的グラフが3選択可能であることを示している．
ちなみに，グラフがk選択可能 (k-choosable) であるとは，各頂点において使用できるk色のリストがどのように与えられても，そのリストに従ったproper coloringが存在することを言う．平面的グラフは4選択可能であるとは限らないが，常に5選択可能であることがThomassenによって証明されている．
A note on emptiness for alternating finite automata with a one-letter alphabet
Petr Jancar and Zdenek Sawa
Information Processing Letters
Volume 104, Issue 5, 30 November 2007, Pages 164-167
http://dx.doi.org/10.1016/j.ipl.2007.06.006
サイズ1のアルファベット上の交代性有限オートマトンが与えられたとき，それの受理する言語が空かどうかを判定する問題はPSPACE完全である (Holzer 1995 DLT)．ここではより簡潔な証明を与えている．
Approximating the minmax rooted-tree cover in a tree
Hiroshi Nagamochi and Kohei Okada
Information Processing Letters
Volume 104, Issue 5, 30 November 2007, Pages 173-178
http://dx.doi.org/10.1016/j.ipl.2007.06.012
辺の重みのついた根付き木が与えられたとき，それをp個の根付き木によって被覆する問題．目的関数はp個の根付き木の中の最大重みの最小化．これはNP困難だけども，この論文では2+ε近似アルゴリズムを提案している．
New length bounds for cycle bases
Michael Elkin, Christian Liebchen and Romeo Rizzi
Information Processing Letters
Volume 104, Issue 5, 30 November 2007, Pages 186-193
http://dx.doi.org/10.1016/j.ipl.2007.06.013
与えられたグラフのサイクル空間のサイクルによる基底の中で長さが短いものを見つける問題．オンラインアルゴリズムなどに応用あり．
それに対して，Deo-Krishnomoorthy-Prabhu (1982 ACM Trans Math Software) の予想を解決したり，Elkin-Emek-Spielman-Teng (2005 STOC) の結果を改善したりしている．
Simulated Annealing versus Metropolis for a TSP instance
Klaus Meer
Information Processing Letters
Volume 104, Issue 6, 16 December 2007, Pages 216-219
http://dx.doi.org/10.1016/j.ipl.2007.06.016
Simulated AnnealingがMetropolisアルゴリズムよりもいい性能を持つような自然な問題があるかどうかJerrum-Sinclairは尋ねていたが，Wegener (2005 ICALP) はある最小費用全域木問題のインスタンスに対してそのようなことが起こることを (理論的に) 示していた．この論文では同様に巡回セールスマン問題のインスタンスにもそのようなものがあることを (理論的に) 示している．局所探索としては2-optを考えている．
New upper bound for the #3-SAT problem
Konstantin Kutzkov
Information Processing Letters
Volume 105, Issue 1, 31 December 2007, Pages 1-5
http://dx.doi.org/10.1016/j.ipl.2007.06.017
O*(1.6423^n)時間で与えられた3CNF式の充足割当を数え上げるアルゴリズム．DPLLタイプ．
A linear time deterministic algorithm to find a small subset that approximates the centroid
Pratik Worah and Sandeep Sen
Information Processing Letters
Volume 105, Issue 1, 31 December 2007, Pages 17-19
http://dx.doi.org/10.1016/j.ipl.2007.07.008
空間中のn個の点が与えられて，その中からO(1/ε)個を選んで重心を1+ε近似する方法．線形時間でdeterministic．手法はInaba-Katoh-Imai (1994 SoCG) の脱乱択化による．
Aspect-ratio Voronoi diagram and its complexity bounds
Tetsuo Asano
Information Processing Letters
Volume 105, Issue 1, 31 December 2007, Pages 26-31
http://dx.doi.org/10.1016/j.ipl.2007.07.010
三角形のアスペクト比をその辺の最大長とその幅の比とする．三角形ABCの内部の点PがABCのアスペクト心 (aspect center) であるとはPAB，PBC，PCAのアスペクト比が全て同じになることとする．任意の三角形にはアスペクト心が一意に存在することが示される．また，平面上に線分がいくつか与えられて，平面全体を線分が与えるアスペクト比に応じて分解する．すなわち，点pが線分sに関わる領域に属することを，sとpの作る三角形のアスペクト比が他の線分とpの作るアスペクト比以上になることとするのである．この分割をアスペクト比ボロノイ図と呼ぶことにして，その組合せ複雑さがO(n^{2+ε})，Ω(n^2)になることを示している．
