演習問題の解答

先日書いた「演習問題の解答」について，八森さんから「いいこと書いてる」という評をいただいた (2006/11/6のところ)．
ありがとうございます．
ちなみに八森さんは私が修士まで暮らした研究室の先輩です．

Domination analysis for minimum multiprocessor scheduling

Gregory Gutin, Tommy Jensen, and Anders Yeo
Discrete Applied Mathematics
Volume 154, Issue 18 , 1 December 2006, Pages 2613-2619
http://dx.doi.org/10.1016/j.dam.2006.02.010

Domination analysis (支配解析とでも訳すのだろうか) に関する論文。
Glover and Punnen (1997) が提唱しているdomination analysisをGutinらは精力的に研究しつづけている。
精力的なのは彼らだけに思えるが、それでもちゃんとやりつづけている根気はすごい。

実行可能集合が有限な最適化問題 (典型的には組合せ最適化問題) Pに対する (厳密に解くとは限らない) アルゴリズムAを考える。
問題PのインスタンスIに対するAの出力値をA(I)と書くことにして、Iの実行可能解の中で目的関数値がA(I)以下のものの割合を考える。
この割合がAのIに対する支配比 (domination ratio) と呼ばれるもので、これが大きければ大きいほど (1に近ければ近いほど) 厳密アルゴリズムに近い、ということになる。
これはアルゴリズムの出力値と最適値を比較する「近似比」という概念に比べて頑健であることが分かる。
例えば、目的関数を2乗すると近似比は変わってしまうが支配比は変わらない。

今、サイズsのインスタンスI全体における支配比のsupremumをdomr(A,s)と書くことにする。
このsを無限大に持っていったときのdomr(A,s)の極限が1となるような多項式時間アルゴリズムAのことをADROアルゴリズムと呼ぶことにする。
ADROはasymptotic domination ratio oneの略。
Alon, Gutin and Krivelevich (2004) は分割問題に対するADROアルゴリズムを提案した。
この問題は2機械スケジューリングに対応するが、本論文ではそれを他機械スケジューリングに拡張して、ADROアルゴリズムを導いている。

考えている問題はいわゆる他機械スケジューリングで、p個の機械はすべて同一で並列処理が可能であり、最終完了時刻 (makespan) を最小化するものである。
アルゴリズムは次のようなものである。インスタンスのサイズはsで、ジョブの数はnであるとする。
まずsがpのn乗以上の場合、n個のジョブをp個の機械へ割り当てる場合の数が高々オーダーpのn乗なので、sに関する多項式時間で最適に解くことができる。
よって、sがpのn乗よりも小さい場合を考える。
この場合、まずn個のジョブの中から処理時間の大きいものを順にr個とってくる。ただしrは(log n/log p)の切り上げ。
そして、これらr個のジョブに関して最適に問題を解く。
次に残されたジョブについては、また処理時間の大きいものから順にp個の機械中負荷がもっとも小さいところへ貪欲に割り当てていく。
これがアルゴリズムであり、論文ではADROアルゴリズムであることが証明されている。

Axiomatic characterizations of generalized values

Jean-Luc Marichal, Ivan Kojadinovic, and Katsushige Fujimoto
Discrete Applied Mathematics
Volume 155, Issue 1, 1 January 2007, Pages 26-43
http://dx.doi.org/10.1016/j.dam.2006.05.002

協力ゲーム理論における「値 (value)」の概念はゲームの集合からプレイヤーの集合への関数であるが、それをゲームの集合から提携全体の集合への関数に拡張したものを考える。
これが「一般化値 (generalized value)」で、提唱者はMarichal (2000) だそうである。
例えば、Shapley値に対して一般化Shapley値のようなものが定義できる。
この論文では、probabilistic generalized valueとgeneralized semivalueというものを考えて、公理系を導いている。

Routing vertex disjoint Steiner-trees in a cubic grid and connections to VLSI

Andras Recski, and David Szeszler
Discrete Applied Mathematics
Volume 155, Issue 1, 1 January 2007, Pages 44-52
http://dx.doi.org/10.1016/j.dam.2006.05.010

2次元のw×nグリッドの上のシュタイナーネットワーク問題を考える。
しかし、解が存在するとは限らないので、次のようにして条件を緩める。
1つはw×nのグリッドを細分して(s×w)×(s×n)のグリッドを考えることにする。
もう1つは次元を1つ増やして、つまり全体として(s×w)×(s×n)×hというグリッドを考えることにする。
このグリッド上でシュタイナーネットワークを構成するのである。
定理として、s≧2のとき、hを6max(w,n)とするネットワークが多項式時間で構成可能であることが示されている。
高さhの下界としてΩ(max(w,n))を示すこともできるが、比例定数の真実がどこら辺なのかは未解決のようだ。

Execution time analysis of a top-down R-tree construction algorithm

Houman Alborzi, and Hanan Samet
Information Processing Letters
Volume 101, Issue 1, 16 January 2007, Pages 6-12
http://dx.doi.org/10.1016/j.ipl.2006.07.010

一部ではやっていて、いまや「標準」といってもよいほどの幾何データ構造となったR-木に関する論文。
この論文では、Garcia, Lopez, and Leutenegger (1998) が提案したbulk loadingによるR-木構成アルゴリズムを少し改変して、計算量解析をしている。

R-Trees: Theory and Applications

R-Trees: Theory and Applications (Advanced Information and Knowledge Processing)

R-木だけに焦点を絞った本。なんとマニアックな！
この本をある図書館で見たとき、異様にほしくなったけど、まだ買ってない。

Hardness results on the man-exchange stable marriage problem with short preference lists

Eric Mc Dermid, Christine Cheng, and Ichiro Suzuki
Information Processing Letters
Volume 101, Issue 1, 16 January 2007, Pages 13-19
http://dx.doi.org/10.1016/j.ipl.2006.07.005

安定結婚問題に関する論文。
Irvingは最近「man-exchange stable matching」という概念を提出したようで、それにはman-exchange blocking pairとい概念を定義すればよい。
マッチングにおけるman-exchange blocking pairとは男性のペアでその2人のパートナーを入れ替えた方が両方ともうれしくなるもののこと。
このとき、man-exchange blocking pairを持たない安定マッチングをman-exchange stable matchingと呼ぶ。
問題はman-exchange stable matchingの存在性である。
Irvingはこの問題がNP完全であることを証明し、さらに男女の選好リストに3人までしか名前を書けない場合には多項式時間アルゴリズムを設計した。
この論文ではリストに書ける人数が4以上の任意の定数である場合には問題がNP完全になることを示している。の

An improved approximation ratio for the minimum linear arrangement problem

Uriel Feige and James R. Lee
Information Processing Letters
Volume 101, Issue 1, 16 January 2007, Pages 26-29
http://dx.doi.org/10.1016/j.ipl.2006.07.009

グラフの最小linear arrangement問題に対する近似アルゴリズム。
Arora, Rao and Vazirani (2004) による有限距離空間の埋め込み技法とRao and Richa (2004) の近似アルゴリズムを組み合わせて、O(\sqrt{log n}loglog n)近似アルゴリズムを設計している。
Rao and Richa (2004) のアルゴリズム自体はEven, Naor, Rao and Schieber (2000) による緩和を用いていて、この緩和自体がなかなか面白い。
同じ近似比の同様なアルゴリズムがCharikar, Hajiaghayi, Karloff and Rao (SODA 2006) でも得られている。

Flows in dynamic networks with aggregate arc capacities

Vardges Melkonian
Information Processing Letters
Volume 101, Issue 1, 16 January 2007, Pages 30-35
http://dx.doi.org/10.1016/j.ipl.2006.07.007

動的transshipment problemといえば，Hoppe and Tardos (2000) の結果が有名で，多項式時間で解けることが知られているが，この論文ではcapacityに通常の動的流問題と異なる解釈を与えたバージョンでtransshipment problemを考えている．
通常の解釈では，capacityというのは単位時間に辺へ流れ込むフローの上界である．
しかし，この論文の解釈ではcapacityを任意の時刻で辺に滞留しているフロー量の上界とするのである．
(応用としては「橋」のようなものを思いつかべればよい，と論文に書いてある．)
このバージョンではtransshipment問題がNP完全になることを証明している．
またtime-expanded networkを用いた線型計画問題としての定式化も与え，それを用いれば擬多項式時間アルゴリズムが得られる．

Linear-time algorithms for problems on planar graphs with fixed disk dimension

Faisal N. Abu-Khzam, and Michael A. Langston
Information Processing Letters
Volume 101, Issue 1, 16 January 2007, Pages 36-40
http://dx.doi.org/10.1016/j.ipl.2006.08.006

ACiD2005論文のジャーナル版．
Fellows and Langston (1988) の不思議な論文で提案された「平面的グラフのdisk dimension」という概念について，disk dimensionが有界な平面的グラフに対するアルゴリズムを提案している．
平面的グラフGのdisk dimensionとは，Gが平面上のk個の開円板の補集合上に埋め込むことができ，さらにその埋め込みにおいて全ての頂点がk個の円板のいずれかの境界上に置かれるようにできる，という性質を持つ最小のkのことである．
まず，disk dimensionがkの平面的グラフが与えられたとき，そこから高々2k-2個の頂点を取り除くことでグラフを外平面的にできることが示されている．
これはアルゴリズムを与えることで証明されていて，そのアルゴリズムの計算量はO(3^k n)である (nは頂点数) ．
これを前処理として用いることで，外平面的グラフに対して易しい問題を解くアルゴリズムも提案されている．

Minimal on-line labelling

Richard S. Bird, and Stefan Sadnicki
Information Processing Letters
Volume 101, Issue 1 , 16 January 2007, Pages 41-45
http://dx.doi.org/10.1016/j.ipl.2006.07.011

N人が次々と順番にやって来るので，1列に並んだN個の席に順に座らせることを考える．
ただし，N個の席にはN人を背の順 (などのある線形順序) に従って座らせなければならないが，次にどれくらいの背の高さの人が来るのか前もって分かっていない．
うまくいかない場合にはその時点までに座った人に動いてもらう必要がある．
そのような再配置の回数を最小にするようなアルゴリズムはどんなものか，この論文は考察している．
これは順序を保ったままリストを更新する問題の特殊な場合で，さらにその更新が挿入だけのsemi-dynamicバージョンである．
知られているアルゴリズム (Zhang 1993, Andersson and Lai 1990) では再配置回数がO(N log^3 N)になるが，少しややこしいらしい．
この論文ではそのアルゴリズムを解説して，単純化した解析を紹介している．
下界もΩ(N log^3 N)となることが予想されているが，まだ分かっていないらしい．