岩間研究室 発表論文
1998年度
[ 論文誌 ]
- id=1998-02
- 宮崎修一, 岩間一雄,
- ``NP完全集合によるcoNP集合の近似とその応用について'',
- 電子情報通信学会論文誌, vol.J81-D-I, no.6, pp.677--684, 1998年 6月.
-
-
>> Abstract
[ 国際会議 ]
- id=1998-03
- K. Iwama, and E. Miyano,
- ``New Bounds for Oblivious Mesh Routing'',
-
Proc. SPAA98 Revue, Jun. 1998.
- id=1998-07
- K. Iwama,
- ``Traffic Control for Cities of Mesh Structure'',
-
Dagstuhl-Seminar on Graph Algorithms and Applications, 98301, Jul. 1998.
-
- (invited talk)
- id=1998-08
- K. Iwama, Y. Kambayashi, and E. Miyano,
- ``New Bounds for Oblivious Mesh Routing'',
-
Proc. ESA'98, LNCS 1461, pp.295--306, Aug. 1998.
-
-
>> Abstract
- id=1998-09
- K. Iwama, and C. Iwamoto,
- ``Improved Time and Space Hierarchies of One-Tape Off-Line TMs'',
-
Proc. MFCS'98, LNCS 1450, pp.580--588, Aug. 1998.
-
-
>> Abstract
- id=1998-10
- K. Iwama, M. Nozoe, and S. Yajima,
- ``Optimizing OBDDs Is Still Intractable for Monotone Functions'',
-
Proc. MFCS'98, LNCS 1450, pp.625--635, Aug. 1998.
-
-
>> Abstract
- id=1998-11
- K. Iwama, E. Miyano, S. Tajima, and H. Tamaki,
- ``Efficient Randomized Routing Algorithms on the Two-Dimensional Mesh of Buses'',
-
Proc. COCOON'98, LNCS 1449, pp.229--240, Aug. 1998.
-
-
>> Abstract
- id=1998-14
- K. Iwama, and E. Miyano,
- ``An $O(\sqrt{N})$ Oblivious Routing Algorithms for 2-D Meshes of Constant Queue-Size'',
-
Proc. SODA'99, pp.466--475, Jan. 1999.
-
-
>> Abstract
- id=1998-15
- K. Iwama, S. Miyazaki, and Y. Morita,
- ``Stable Marriage with Incomplete Lists and Ties'',
-
Proc. the 1st Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (JHSDMIA'99), pp.63--70, Mar. 1999.
-
-
>> Abstract
[ 国内発表 ]
- id=1998-01
- 宮野英次, 岩間一雄,
- ``メッシュ上での無情報ラウティングアルゴリズム'',
- 電子情報通信学会 コンピュテーション研究会, 信学技報, vol.98, no.36, COMP98-8, pp.57--64, 1998年 4月.
-
-
>> Abstract
- id=1998-04
- 宮崎修一, 岩間一雄,
- ``部分MAXSATを利用した大学情報処理の自動化'',
- 情処研報, vol.98, no.58, 98-DBS-116(2), pp.335--342, 1998年 7月.
-
-
>> Abstract
- id=1998-05
- 宮崎修一, 岩間一雄,
- ``バックトラック法を用いた導出原理の複雑さの解析について'',
- 情報基礎理論ワークショップ98 予稿集, pp.13--18, 1998年 7月.
-
-
>> Abstract
- id=1998-06
- 岩本宙造, 岩間一雄,
- ``1テープオフラインTMの時間量と領域量の稠密な階層'',
- 情報基礎理論ワークショップ98 予稿集, pp.102--107, 1998年 7月.
-
-
>> Abstract
- id=1998-12
- 宮野英次, 岩間一雄,
- ``2次元メッシュ上での無情報ラウティング'',
- 情報処理学会アルゴリズム研究会, 情処研報, vol.98, no.78, pp.25--32, 1998年 9月.
-
-
>> Abstract
- id=1998-13
- 宮崎修一, 岩間一雄,
- ``条件を緩和した安定結婚問題のNP完全性について'',
- 電子情報通信学会 コンピュテーション研究会, 信学技報, vol.98, no.432, COMP98-55, pp.33--40, 1998年 11月.
-
-
>> Abstract
- id=1998-16
- 盛田保文, 宮崎修一, 岩間一雄,
- ``条件を緩和した安定結婚問題の複雑さ'',
- 情報処理学会アルゴリズム研究会, 情処研報, vol.99, no.26, pp.15--22, 1999年 3月.
-
-
>> Abstract
- id=1998-17
- 内田敦, 宮崎修一, 岩間一雄,
- ``オンライン問題のクラス分け'',
- 第58回(平成11年後期)情処全国大会講演論文集, vol.1, pp.319--320, 1999年 3月.
- id=1998-18
- 荒木孝子, 岡部寿男,
- ``災害時に耐障害性を有するネットワークのためのルーティング'',
- 第58回(平成11年後期)情処全国大会講演論文集, vol.3, pp.401--402, 1999年 3月.
- id=1998-19
- 呉屋健, 岡部寿男, 岩間一雄,
- ``Oblivious Branching Program のサイズの下限について'',
- 1999年電子情報通信学会総合大会講演論文集, vol.1, D-1-2, 1999年 3月.
- id=1998-20
- 山田克樹, 岡部寿男, 岩間一雄,
- ``単調のDNF式と$k$CNF式の等価性判定アルゴリズム'',
- 1999年電子情報通信学会総合大会講演論文集, vol.1, D-1-3, 1999年 3月.
Abstract
-
id=1998-01
- 本稿では，メッシュネットワーク上での無情報ラウティングについて，2つの
新しい上限を与える．まず，各プロセッサが持つキューの大きさを定数に限定
した2次元メッシュモデル上での$O(N^{0.75})$時間のラウティングアルゴリズ
ムを示す．本アルゴリズムは，自明な$O(N)$時間の上限を実質的に改善した最
初のアルゴリズムである．次に，キューの大きさを限定しない3次元メッシュ
モデル上での$1.16\sqrt{N}+o(\sqrt{N})$時間のアルゴリズムを示す．本アル
ゴリズムは，パケットの移動経路の曲がる回数を高々3回までしか許さない．
もし曲がる回数を最小，つまり，高々2回に限定すると，ラウティング時間が
$\Omega(N^{2/3})$まで飛躍的に大きくなることが知られている．
-
id=1998-02
- クラス$C_{1}$に属する集合$L_{1}$が，クラス$C_{2}$に属する集合$L_{2}$の
部分集合であるとき，$L_{1}$は$L_{2}$の近似であるという．$L_{1}\subset
L'_{1}$，$L'_{1}-L_{1}$が無限集合となるような近似$L'_{1}$が存在しない
とき，$L_{1}$は最適近似であるという．$C_{1}$がクラスP，$C_{2}$がクラス
NPである場合には，P$\neq$ NPならば弱い条件の元で最適な近似が存在しない
ことが示されている．本論文では，$C_{1}$がNP完全集合のクラスで，$C_{2}$
がcoNPである場合に対し，同様の結果を示す．coNP集合のNP完全集合による近
似は，組合せアルゴリズムを実験的に評価する際の例題生成の効率に深い関わ
りを持っている．
-
id=1998-04
- 複雑ではあるがそれほど大規模でないデータベース上の情報処理の高速化を
目標とする．本研究では，組み合わせ問題（SAT）を利用してデータベース上の
問題を解くという方針をとる．変換アルゴリズムの構築が容易であることと，
SATに対する既存の高速アルゴリズムを利用できるといった利点が考えられる．
本稿では大学情報処理の一つである研究室配属問題を部分MAXSATに変換して解
くことを試みた．ランダム例題を用いて，我々の方法と研究室配属問題を直接
解くアルゴリズムとを比較した．その結果，変換を用いた方法がある程度有効
であることが分かった．
-
id=1998-05
- 鳩の巣原理に対する導出原理による証明の非多項式下限を示す．鳩の巣原理
に対する指数下限は既に知られているが，その証明は理解しにくいものであっ
た．本稿では，バックトラック法と導出原理の関係を利用することにより，証
明をかなり簡単化できることを示す．
-
id=1998-06
- 本稿では，１テープオフラインTMの時間量と領域量の階層定理を改善する．
(i) $\inf_{n\rightarrow\infty}\frac{t_1(n)\log\log t_1(n)}{t_2(n)}=0$
と$t_1(n)=n^{O(1)}$を満たす任意の時間構成可能関数$t_1(n),t_2(n)$に対し
て，いかなる$t_1(n)$時間TMでも受理できないが，ある$t_2(n)$時間TMで受理
できる言語が存在する．(ii) 任意の領域構成可能関数$s(n)$に対して，いか
なる２記号TMでも$s(n)$領域では受理できないが，$s(n)+\log
s(n)+(2+\epsilon)\log\log s(n)$領域なら受理できる言語が存在する．
-
id=1998-08
- We give two, new upper bounds for oblivious permutation
routing on the mesh network. One is an $O(N^{0.75})$ algorithm for the
two-dimensional mesh with constant queue-size. This is the first
algorithm which improves substantially the trivial $O(N)$ bound. The
other is an $1.16\sqrt{N}+o(\sqrt{N})$ algorithm on the
three-dimensional mesh with unlimited queue-size. This algorithm allows
at most three bends in the path of each packet. If the number of bends
is restricted to minimal, i.e., at most two, then the bound jumps to
$\Omega(N^{2/3})$ as was shown in ESA'97.
-
id=1998-09
- This paper presents improved time and space hierarchies of one-tape
off-line TMs: (i) For any time-constructible functions $t_1(n)$ and
$t_2(n)$ such that $\inf_{n\rightarrow\infty}\frac{t_1(n)\log\log
t_1(n)}{t_2(n)}=0$ and $t_1(n)=n^{O(1)}$, there is a language which
can be accepted by a $t_2(n)$-time TM, but not by any $t_1(n)$-time
TM. (ii) For any space-constructible function $s(n)$ and positive
constant $\epsilon$, there is a language which can be accepted in
space $s(n)+\log s(n)+(2+\epsilon)\log\log s(n)$ by a TM with two
worktape-symbols, but not in space $s(n)$ by any TM with the same
worktape-symbols.
-
id=1998-10
- Optimizing the size of Ordered Binary Decision Diagrams is
shown to be NP-complete for monotone Boolean functions.
The same result for general Boolean functions was obtained by Bollig
and Wegener recently.
-
id=1998-11
- 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=1998-12
- 2次元メッシュ計算機上での$O(\sqrt{N})$時間の無情報ラウティング
アルゴリズムを示す．本モデルは，$\sqrt{N}\times \sqrt{N}$個のプロセッサを
点対点結合した標準的なメッシュモデルであり，それぞれのプロセッサは，
定数個までのパケットを一度に保持することができるキューを持つ．これまでに
知られていた上限は$O(N^{0.75})$である．
-
id=1998-13
- 安定結婚問題は，入力として$N$人ずつの男女と各
個人の異性に対する希望リスト（異性$N$人の順序付け）が与えられ，安定な
$N$組のペアを求める（安定な$N$組のペアが存在するかどうかを問う）問題で
ある．本問題の自然な拡張として，(i)希望リストに異性$N$人全員を書かなく
ても良いもの，(ii)希望の順序付けに半順序を許すもの，があるが，いずれも
解の存在は多項式時間で判定できることが知られている．本研究では，(i)お
よび(ii)を同時に許した場合に，本問題がNP完全になることを示す．また，本
問題に関連した問題のNP完全性も示す．
-
id=1998-14
- An $O(\sqrt{N})$ {\it oblivious} permutation-routing algorithm for
2-dimensional meshes is presented. The model is a standard mesh where
$\sqrt{N}\times \sqrt{N}$ processors are connected via point-to-point
connections and each processor has a queue which can hold only a
constant number of temporal packets. The previous bound was
$O(N^{0.75})$.
-
id=1998-15
- The original stable marriage problem requires both man and woman to
submit a complete and a strict order of his/her preference, i.e., a
totally ordered list of, say, 100 people. This is obviously
unrealistic often in practice, and several relaxations have been
proposed including the following two common ones: One is to allow an
incomplete list, i.e., a man is allowed to accept only a subset of the
women and vice versa. The other is to allow a preference list
including ties. Fortunately, it is known that both relaxed problems
can still be solved in polynomial time. In this paper, we show that
the situation changes substantially if we allow both relaxations
(incomplete lists and ties) {\it at the same time}: The problem not
only becomes NP-hard but also there are no approximation algorithms
achieving the approximation ratio of $N^{1-\epsilon}$, where $N$ is
the size of instances, unless P=NP.
-
id=1998-16
- 安定結婚問題とは, $N$人ずつの男女と各個人が異性に対する好みの順を書い
た希望リストが与えられたときに, 安定な$N$組のペアを求める問題であ
る. 本問題に対しては多項式時間アルゴリズムが存在することが知られている.
また, この問題の希望リストに対する条件の緩和として, 異性全員を書かなく
てもよい場合や, 異性の希望順位に同順位を許す場合などが考えられるが, こ
れらの緩和を単独で用いた場合にも, 解の存在を判定する多項式時間アルゴリ
ズムが知られている. 本稿ではこれらの緩和を同時に行った場合に問題がNP完
全になることを示す. また, 本問題にコストを導入した最適化問題に対して,
近似度の良いアルゴリズムが存在しないことを示す.