岩間研究室 発表論文
2001年度
[ 著書 ]
- id=2001-04
- 岩間一雄,
- アルゴリズム理論入門 (情報系教科書シリーズ 4),
- 昭晃堂, 2001年 5月.
- id=2001-08
- 滝根哲哉, 伊藤大雄, 西尾章治郎,
- ネットワーク設計理論 (岩波講座「インターネット」第５巻),
- 岩波書店, 2001年 6月.
[ 論文誌 ]
- id=2001-01
- 河合大輔, 宮崎修一, 岡部寿男, 岩間一雄,
- ``SATに対する局所探索法のベクトル化'',
- 情報処理学会論文誌, vol.42, no.4, pp.754--761, 2001年 4月.
-
-
>> Abstract
- id=2001-03
- K. Iwama, and E. Miyano,
- ``A Lower Bound for Elementary Oblivious Routing on Three-Dimensional Meshes'',
-
J. Algorithms, vol.39, no.2, pp.145--161, May 2001.
-
-
>> Abstract
- id=2001-09
- K. Iwama, E. Miyano, S. Tajima, and H. Tamaki,
- ``Efficient randomized routing algorithms on the two-dimensional mesh of buses'',
-
Theoretical Computer Science, vol.261, no.2, pp.227--239, Jun. 2001.
-
-
>> Abstract
- id=2001-14
- K. Iwama, Y. Kambayashi, and E. Miyano,
- ``New bounds for oblivious mesh routing'',
-
Journal of Graph Algorithms and Applications, Jul. 2001.
-
-
>> Abstract
- id=2001-26
- K. Iwama, and E. Miyano,
- ``An $O(\sqrt{N})$ oblivious routing algorithm for 2-D meshes of constant queue-size'',
-
Journal of Algorithms, vol.41, no.2, pp.262--279, Nov. 2001.
[ 国際会議 ]
- id=2001-02
- K. Iwama,
- ``Packet Routing and Combinatorics'',
-
Proc. the 2nd Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Apr. 2001.
-
- (invited talk)
- id=2001-10
- M. Halld\'orsson, K. Iwama, S. Miyazaki, and Y. Morita,
- ``Inapproximability of Stable Marriage Problems'',
-
Proc. 6th KOREA-JAPAN Joint Workshop on Algorithms and Computation (WAAC 2001), pp.59--66, Jun. 2001.
-
-
>> Abstract
- id=2001-11
- K. Iwama, and S. Tamaki,
- ``Exploiting Partial Knowledge of Satisfying Assignments'',
-
Proc. SAT 2001, Jun. 2001.
- id=2001-20
- K. Iwama, Y. Okabe, and T. Takase,
- ``Separating Oblivious and Non-Oblivious BPs'',
-
Proc. COCOON 01, LNCS 2108, pp.28--38, Aug. 2001.
- id=2001-21
- K. Iwama, and S. Tamaki,
- ``Exploiting Partial Knowledge of Satisfying Assignments'',
-
Proc. WAE 01, LNCS 2141, pp.118--128, Aug. 2001.
-
-
>> Abstract
- id=2001-23
- K. Iwama,
- ``Quantum search algorithms for database query processing'',
-
Proc. ERATO workshop on Quantum Information Sience (EQIS 2001), Sep. 2001.
-
- (invited talk)
- id=2001-28
- K. Iwama, and S. Yamashita,
- ``A Complete Set of Transformation Rules for Quantum Boolean Circuits with CNOT gates'',
-
Worshop on Quantum Dots for Quantum Computing and Classical Size Effect Circuits (Special volume of Superlattices and Microstructures), Jan. 2002.
-
-
>> Abstract
[ 国内発表 ]
- id=2001-05
- 松浦昭洋, 岩間一雄,
- ``SATのいくつかの部分問題の複雑さついて'',
- 京都大学数理解析研究所講究録, 1205 (計算理論とアルゴリズムの新展開), pp.113--118, 2001年 5月.
-
-
>> Abstract
- id=2001-06
- 天野正己, 岩間一雄,
- ``量子モデルと確率モデルの確率計算の違いによって生じる計算能力の差について'',
- 京都大学数理解析研究所講究録, 1205 (計算理論とアルゴリズムの新展開), pp.188--193, 2001年 5月.
- id=2001-07
- 玉置卓, 岩間一雄,
- ``SAT充足解の偏りを利用した局所探索の高速化'',
- 電子情報通信学会 コンピュテーション研究会, 信学技報, vol.101, no.44, COMP 2001-11, pp.49--56, 2001年 5月.
-
-
>> Abstract
- id=2001-15
- Rudy Raymond H.P., 天野正己, 岩間一雄,
- ``一方向量子有限オートマトンの初期状態の不完全性'',
- 情報処理学会 アルゴリズム研究会, 2001-AL-79, pp.7--12, 2001年 7月.
-
-
>> Abstract
- id=2001-16
- 米澤弘毅, and 岩間一雄,
- ``Axis-bound CNN Problem'',
- 京都大学数理解析研究所講究録, 1241 (数理最適化の理論とアルゴリズム), pp.48--56, Jul. 2001.
-
-
>> Abstract
- id=2001-17
- 柳澤弘揮, 宮崎修一, 岩間一雄, M. Halld\'orsson,
- ``条件を緩和した安定結婚問題に対する確率近似アルゴリズム'',
- 2001年夏のLAシンポジウム予稿 (LAシンポジウム), pp.4.1--4.11, 2001年 7月.
-
-
>> Abstract
- id=2001-18
- 河内亮周, 岩間一雄,
- ``量子探索アルゴリズムのデータベース質問処理への応用'',
- 2001年夏のLAシンポジウム予稿 (LAシンポジウム), pp.5.1--5.7, 2001年 7月.
-
-
>> Abstract
- id=2001-19
- 山下茂, 岩間一雄,
- ``ブール関数を計算する量子回路の局所変換ルールの完全集合'',
- 情報処理学会 アルゴリズム研究会, 情処研報, 2001-AL-79, pp.13--20, 2001年 7月.
-
-
>> Abstract
- id=2001-24
- 河内亮周, 岩間一雄,
- ``量子探索アルゴリズムのデータベース質問処理への応用'',
- 電子情報通信学会 量子情報技術研究会 (QIT5), QIT2001-19, pp.99--104, 2001年 11月.
-
-
>> Abstract
- id=2001-25
- 河内亮周, 山下茂, 岩間一雄,
- ``占有問題に対する量子アルゴリズム'',
- 電子情報通信学会 コンピュテーション研究会, 信学技報, vol.101, no.431, COMP2001-56, pp.31--36, 2001年 11月.
-
-
>> Abstract
- id=2001-27
- 武富史郎, 岩間一雄,
- ``複数個の解候補を保持できるオンラインナップサック問題'',
- 電子情報通信学会 コンピュテーション研究会, 信学技報, vol.101, no.488, COMP2001-72, pp.71--78, 2001年 12月.
-
-
>> Abstract
- id=2001-29
- 松浦昭洋,
- ``一定数の充足解を持つCNF式に対する準指数時間アルゴリズム'',
- 電子情報通信学会 コンピュテーション研究会, 信学技報, vol.101, no.630, COMP2001-76, pp.17--23, 2002年 1月.
-
-
>> Abstract
- id=2001-30
- 河内亮周, 山下茂, 岩間一雄,
- ``負荷分散に対する量子サンプリング'',
- 2001年冬のLAシンポジウム予稿 (LAシンポジウム), pp.26.1--26.11, 2002年 2月.
-
-
>> Abstract
- id=2001-31
- 柳澤弘揮, 宮崎修一, 岩間一雄, M. Halld\'orsson,
- ``条件を緩和した安定結婚問題に対する近似アルゴリズム'',
- 2001年冬のLAシンポジウム予稿 (LAシンポジウム), pp.40.1--40.8, 2002年 2月.
- id=2001-32
- 今村友和, 岩間一雄,
- ``全域的に疎なグラフに対する最小頂点被覆問題'',
- 2002年電子情報通信学会総合大会講演論文集, D-1-4, 2002年 3月.
- id=2001-33
- 沖田正樹, 岩間一雄,
- ``伸張係数２のコンパクトルーティング'',
- 2002年電子情報通信学会総合大会講演論文集, D-1-5, 2002年 3月.
- id=2001-34
- 戸田充彦, 山下茂, 岩間一雄,
- ``Mathematicaと並列計算機を併用した量子計算のシミュレーション'',
- 2002年電子情報通信学会総合大会講演論文集, D-1-8, 2002年 3月.
- id=2001-35
- 吉廣卓哉, 伊藤大雄, 岡部寿男, 岩間一雄,
- ``無線LANにおける動的なループフリールーティング'',
- 2002年電子情報通信学会総合大会講演論文集, SB-9-14, 2002年 3月.
[ 解説 ]
- id=2001-12
- 岩間一雄,
- ``オンラインアルゴリズム'',
- bit別冊「アルゴリズム工学」, pp.74--80, 2001年 6月.
- id=2001-13
- 伊藤大雄,
- ``2次元ハムサンドイッチ定理の一般化'',
- bit別冊「アルゴリズム工学」, pp.154--159, 2001年 6月.
- id=2001-22
- 岩間一雄,
- ``CNF充足可能性判定問題の計算複雑さ −最近の発展−'',
- 人工知能学会誌, vol.16, no.5, pp.636--641, 2001年 9月.
Abstract
-
id=2001-01
- 本研究の目的は，和積形論理式の充足可能性問題(SAT)の解法アルゴリズムで
ある局所探索法の高速化である．局所探索法のアルゴリズムGSATに対し，実働
化時の工夫と並列化によって高速化を試みる．SelmanとKautzのGSATを元に，
(i)~データ構造の改良，(ii)~ベクトル並列計算機上でのベクトル化，
(iii)~PVMを使った40CPUによる並列化，を行った．これにより，合計600倍の
高速化を達成した．2nd DIMACS Implementation Challenge, Satisfiability
のベンチマーク例題に対して我々のGSATを実行させたところ，既存のプログラ
ムで解けている例題では実行時間がかなり短縮された．また，GSATを改良した
局所探索法に本論文の手法を適用させることにより，既存のプログラムでは解
けなかった例題を解くまでに至った．
-
id=2001-03
- メッシュ結合型並列計算機は，次元を大きくしていくのに従い，モデルとし
ての能力も高くなっていくというのが一般的な常識となっている．しかし，本
論文では，基本的なネットワーク演算の一つであるラウティングに対して，
$N$をプロセッサの総個数とした場合，2次元メッシュ結合型モデル上では
$O(\sqrt{N})$時間でラウティング可能であるのに対して，3次元メッシュ結合
型モデル上では少なくとも$O(N^{2/3})$時間を必要とすることを示している．
-
id=2001-05
- 本稿では、充足可能性問題(SAT) の部分問題の複雑さについて考察する。
まず、$n$変数$k$-CNF式$\phi$が高々$pn$個($0 \le p \le 1$)しか1となる変数
を含まないような充足解を持つかどうかを問う決定問題を考える。我々は、$k
\ge 2$に対して、(1)$p=n^c$ ($-1 < c \le 0$)ならば、その決定問題はNP完
全であり、(2)$p=\log n / n$ならば、$O(n^{\log k} |\phi|)$時間で解ける
ことを示す。また、充足解の数の上限、下限に関する情報があらかじめ分かっ
ている場合に充足解を求める問題の複雑さについても考察する。
-
id=2001-07
- Schoening の k-SAT アルゴリズムは, 現在知られている 3-SATの最も高速な
確率的アルゴリズムである. 本研究では，このアルゴリズムの改良と応用を試
みる. まず, 与えられた論理式の充足解に現れる 0 と 1の個数が分かってい
る場合に, 良い初期値を選ぶことが可能であり, 高速化が可能であることを示
した. この応用として NP 完全問題で, SATに帰着したときに充足解に現れる
0 と 1 の個数が分かっている3次元マッチング問題にアルゴリズムを適用して,
その問題に対する総当たりのアルゴリズムとの計算時間の比較を行ない自明で
ない上限を示す.
-
id=2001-09
- The mesh of buses (MBUS) is a parallel computation model which
consists of $n \times n$ processors, $n$ row buses and $n$ column
buses but no local connections between two neighboring processors. As
for deterministic (permutation) routing on MBUSs, the known $1.5n$
upper bound appears to be hard to improve. Also, the information
theoretic lower bound for any type of MBUS routing is $1.0n$. In this
paper, we present two randomized algorithms for MBUS routing. One of
them runs in $1.4375n+o(n)$ steps with high probability. The other
runs $1.25n+o(n)$ steps also with high probability but needs more
local computation.
-
id=2001-10
- The stable marriage problem has received considerable attention both
due to its practical applications as well as its mathematical
structure. While the original problem has all participants rank all
members of the opposite sex in a strict order of preference, two
natural variations are to allow for incomplete preference lists and
ties in the preferences. Both variations are polynomially solvable by a
variation of the classical algorithm of Gale and Shapley. On the
other hand, it has recently been shown to be NP-hard to find a maximum
cardinality stable matching when both of the variations are allowed.
We show here that it is APX-hard to approximate the maximum
cardinality stable matching with incomplete lists and ties. This holds
for some very restricted instances both in terms of lengths of
preference lists and lengths and occurrences of ties in the lists. We
also obtain optimal $\Omega(N)$ hardness results for 'egalitarian' and
'minimum regret' variants.
-
id=2001-14
- メッシュ結合モデル上での無情報ラウティングについて論じている．本論文
では，定数サイズのキューを有する2次元メッシュ結合モデル上での
$O(N^{0.75})$時間の上限を示している．従来の自明な$O(N)$時間の上限を本
質的に改良した最初の結果である．また，3次元メッシュ結合モデル上での
$1.16\sqrt{N} + o(N)$時間の上限を示している．本アルゴリズムは，パケッ
トの移動経路の曲がる回数を高々3回までしか許さない．
-
id=2001-15
- 本稿では、1QFA(一方向量子有限オートマトン)の初期状態が不完全な場合、
最終的な受理確率にどのような影響を与えるかについて述べる. 具体的には、
初期状態が$\left|\Psi\right>$と$\left|\Psi'\right> =
\sqrt{1-\delta}\left|\Psi\right> +\sqrt{\delta} \left|\epsilon\right>$
で、それ以外は同じ2つのQFAの受理確率の差が同じ入力に対して高々
$\sqrt{\delta}$であることを示す.
-
id=2001-16
- The CNN Problem is a kind of a one-server problem in which a request
moves on the two-dimensional plane. If the request appears at position
$(i,j)$, the server does not have to move to the place $(i,j)$ itself
but has only to move somewhere given by $(i,l)$ or $(k,j)$. Namely it
is enough to move either to the same row or to the same column. The
goal is to minimize the total moving distance of the server. This
problem has been quite popular for the last several years but it is
still open whether or not there is a competitive algorithm, i.e., an
algorithm whose competitive ratio is bounded by a constant. In this
paper we consider a natural restriction of the problem, namely, the
server can move only on the $X$-axis and $Y$-axis, which can be viewed
as a one-dimensional version of the original problem. It is shown that
there is an online algorithm for this ``axis-bound CNN'' whose
competitive ratio is at most $9.0$.
-
id=2001-17
- While the original stable marriage problem requires all participants
to rank all members of the opposite sex in a strict order, two natural
variations are to allow for incomplete preference lists and ties in
the preferences. Either variation is polynomially solvable, but it
has recently been shown to be NP-hard to find a maximum cardinality
stable matching when both of the variations are allowed. It is easy
to see that the size of any two stable matchings differ by at most a
factor of two, and so, approximation of factor two is trivial. In
this paper, we give a first nontrivial result for approximation of
factor less than two. Our randomized algorithm achieves a factor of
$32/23$ for a restricted case, where ties occur in only men's lists,
each man writes at most one tie, and the length of tie is two.
Furthermore, we show that these restrictions except for the last one
can be removed with keeping the approximation ratio less than two.
-
id=2001-18
- 与えられた2つの関数$f:X\rightarrow Y, g:Y\rightarrow Z$に対して
$f(x)=g(y)$を満たす$(x,y)$を見つけるといったクロー探索問題
(Claw-finding)を考える。$|X|=n, |Y|=m, m\geq n$とした場合に決定性の計
算モデルにおける$f,g$の評価回数は$O(m\log n)$だが、量子計算モデルでは
Groverの量子探索アルゴリズム\cite{Gro96}を巧妙に利用した$f,g$の評価回
数が$O(n^{1/2}m^{1/4}\log n)$($|X|=|Y|=n$では$O(n^{3/4}\log n)$)ですむ
アルゴリズムが示されている\cite{BDHHMSW00}。本研究ではこの結果を3つの
関数の場合に拡張を行う。\cite{BDHHMSW00}で示されているアルゴリズムは量
子計算の中にランダムサンプリングを用いているが、本稿ではランダムサンプ
リングを用いずに全て量子計算モデルに基づく簡便で詳細な記述な与える。こ
の結果を利用して、3つの関数$f:X \rightarrow W, g:Y\rightarrow W,
h:Z\rightarrow W$のクロー探索問題に対して$|X|=|Y|=|Z|=n$とした場合にあ
る条件の下で$f,g,h$の評価回数が線型を下回る$O(n^{7/8}\log n)$である量
子アルゴリズムを示す。このような拡張は3つの表(あるいはそれ以上)の結合
結果に対する質問処理とみなすことができ、実用的な意味も備えている。
-
id=2001-19
- 本稿では，CNOT(制御NOT)ゲートにより構成されるブール関数を計算する量子
回路における，回路の局所変換ルールの集合について述べる. 本稿で述べる局
所変換ルールの集合は単純であるが自明ではない. また，その集合が完全であ
ること，つまり，任意の二つの回路に対して一方から他方への変換が本稿で述
べるルールのみを適用することによって可能であることも示す.
-
id=2001-21
- Recently Sch\"oning has shown that a simple local-search algorithm
for 3SAT achieves the currently best upper bound, i.e., an expected
time of $1.334^n$. In this paper, we show that this algorithm can be
modified to run much faster if there is some kind of imbalance in
satisfying assignments and we have a (partial) knowledge about
that. Especially if a satisfying assignment has imbalanced 0's and
1's, i.e., $p_1 n$ 1's and $(1-p_1)n$ 0's, then we can find a solution
in time $1.260^n$ when $p_1=1/3$ and $1.072^n$ when $p_1=0.1$. Such an
imbalance often exists in SAT instances reduced from other
combinatorial problems. As a concrete example, we investigate a
reduction from 3DM and show our new approach is nontrivially faster
than its direct algorithms. Preliminary experimental results are also
given.
-
id=2001-24
- 本研究では最近発表された量子クロー探索アルゴリズムをデータベース質問
処理の一つであるジョインに応用する。２関数のクロー探索はそのまま２つの
表の場合に利用できるが、３つの表の場合にはそのままでは利用できない。本
研究では量子的な中間解を上手く利用することで高速化の達成を目指す
-
id=2001-25
- 本研究ではネットワーク上における負荷分散に深く関連する占有問題に対す
る量子アルゴリズムについて議論する．静的なモデルにおいては古典アルゴリ
ズムの方が有利である．一方で，動的なモデルの下では量子アルゴリズムの有
利であることを示される．
-
id=2001-27
- オンラインナップサック問題とは, プレイヤがサイズ1のナップサックを持ち,
各時点で1つのサイズ1以下のアイテムが与えられる. プレイヤはそのアイテ
ムをナップサックに入れるか否かを次のアイテムが来る前に決定し, 最終的に
できるだけ合計サイズが大きくなるようにアイテムを入れていくことを目的と
するオンライン問題である. 通常この問題において, プレイヤは1度ナップサッ
クに入れたアイテムを捨てることはできないが, 本研究では捨てても良いもの
とする. 本研究ではこの問題の競合比が1.618となることを示した. さらに
同時に複数個の解を保持することを許したモデルを考察し,その競合比の上限
と下限を与えた.
-
id=2001-28
- This paper gives a simple but nontrivial set of local transformation
rules for CNOT-based quantum circuits. It is shown that this rule set
is complete, namely for any two equivalent circuits, $S_1$ and $S_2$,
there is a sequence of transformations, each of them in the rule set,
which changes $S_1$ to $S_2$. This rule set can be used for
incremental circuit optimization methods like the classical circuit
design methodology.
-
id=2001-29
- 本稿では、実行時間と充足解の総数の間にトレードオフを持つCNF式に対する
効率的なアルゴリズムを示す。アルゴリズムでは、まず非充足解の総数を求め
るInclusion-Exclusion公式、及びその数の近似に基づいて、充足性判定アル
ゴリズムを構成する。次にその判定アルゴリズムをサブルーチンとして、充足
解を$2^n/\delta$個持つ$n$変数、$m$項のCNF式に対して、
$2^{O(\sqrt{m}\log^{3/2}m \log \delta)}$時間で充足解を求めるアルゴリズ
ムを構成する。特に、$m=o(n^{2 - \epsilon})$、$\delta =
2^{n^{\epsilon}}$のとき、準指数時間のアルゴリズムとなる。
-
id=2001-30
- In the (static) balls-and-bins problem, $M$ balls are placed into $N$
bins, one by one, uniformly at random. In the continuous model, after
$M$ balls have arrived, balls continue arriving one at a unit time,
but a ball which is selected at random again is removed from the bins
at the same time. This paper investigates quantum load balancing which
replaces the random search of the bin which receives a ball by a
single iteration of Grover search. The load of a bin is the number of
balls held by the bin. It is shown that by using the quantum search:
(i) The maximum load can only be improved quadratically for the static
model. (ii) It is improved to $O(1)$ for the continuous model under
reasonable conditions.