# 岩間研究室 発表論文

## [ 論文誌 ]

id=1998-02

NP完全集合によるcoNP集合の近似とその応用について'',

>> 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

メッシュ上での無情報ラウティングアルゴリズム'',

>> Abstract
id=1998-04

部分MAXSATを利用した大学情報処理の自動化'',

>> Abstract
id=1998-05

バックトラック法を用いた導出原理の複雑さの解析について'',

>> Abstract
id=1998-06

1テープオフラインTMの時間量と領域量の稠密な階層'',

>> Abstract
id=1998-12

2次元メッシュ上での無情報ラウティング'',

>> Abstract
id=1998-13

条件を緩和した安定結婚問題のNP完全性について'',

>> Abstract
id=1998-16

条件を緩和した安定結婚問題の複雑さ'',

>> Abstract
id=1998-17

オンライン問題のクラス分け'',

id=1998-18

災害時に耐障害性を有するネットワークのためのルーティング'',

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

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

id=1998-05

id=1998-06

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

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