# 岩間研究室 発表論文

## [ 論文誌 ]

id=1999-06

しきい値関数を表す共有2分決定グラフの最適な変数順序付けの計算複雑度'',

>> Abstract
id=1999-07
S. Miyazaki, and K. Iwama,
Approximation of coNP Sets by NP-complete Sets and Its Applications'',
Systems and Computers in Japan, vol.30, no.7, pp.47--54, Jun. 1999.

>> Abstract
id=1999-08

テープ記号数を制限したチューリング機械の領域階層'',

>> Abstract
id=1999-21
Y. Asahiro, K. Iwama, H. Tamaki, and T. Tokuyama,
Greedily Finding a Dense Subgraph'',
J. Algorithms, vol.34, no.2, pp.203--221, Jan. 2000.

>> Abstract
id=1999-23
K. Iwama, and E. Miyano,
Oblivious Routing Algorithms on the Mesh of Buses'',
J. Parallel and Distributed Computing, vol.60, no.2, pp.137--149, Feb. 2000.

>> Abstract

## [ 国際会議 ]

id=1999-04
M. Amano, and K. Iwama,
Undecidability on Quantum Finite Automata'',
Proc. STOC'99, pp.368--375, May 1999.

>> Abstract
id=1999-05
K. Iwama, and E. Miyano,
New Techniques in 2-D Mesh Routing'',
ACM/UMIACS Workshop on Parallel Algorithms (WoPA'99), May 1999.

>> Abstract
id=1999-09
K. Iwama, D. Manlove, S. Miyazaki, and Y. Morita,
Stable Marriage with Incomplete Lists and Ties'',
Proc. ICALP'99, LNCS 1644, pp.443--452, Jul. 1999.

>> Abstract
id=1999-10
K. Iwama, and E. Miyano,
Multipacket Routing on 2-D meshes and Its Applications to Fault-Tolerant Routing'',
Proc. ESA'99, LNCS 1643, pp.53--64, Jul. 1999.

>> Abstract
id=1999-11
K. Iwama, S. Miyazaki, and A. Uchida,
Hardest Online Problems'',
Proc. KOREA-JAPAN Joint Workshop on Algorithms and Computation (WAAC'99), pp.59--66, Jul. 1999.

>> Abstract
id=1999-13
K. Iwama, and K. Yonezawa,
Using Generalized Forecasts for Online Currency Conversion'',
Proc. COCOON'99, LNCS 1627, pp.409--421, Aug. 1999.

>> Abstract
id=1999-17
K. Iwama,
Oblivious vs. Non-Oblivious Branching Programs'',
Dagstuhl-Seminar on Complexity of Boolean Functions, 99441, Oct. 1999.

(invited talk)
id=1999-19
K. Iwama, and S. Miyazaki,
Tree-Like Resolution Is Superpolynomially Slower Than DAG-Like Resolution for the Pigeonhole Principle'',
Proc. ISAAC'99, LNCS 1741, pp.133--142, Dec. 1999.

>> Abstract

## [ 国内発表 ]

id=1999-01

一方向通貨交換問題における予測を用いたアルゴリズム'',

>> Abstract
id=1999-02

量子有限オートマトンにおける決定不能問題'',

>> Abstract
id=1999-03

オンライン問題の複雑さの解析について'',

>> Abstract
id=1999-12

Syntactic BP と oblivious BP の分離'',
1999年夏のLAシンポジウム予稿 (LAシンポジウム), 1999年 7月.

>> Abstract
id=1999-15

メッシュ上でのビット反転置換を用いたラウティングアルゴリズム'',

>> Abstract
id=1999-16

鳩の巣原理に対する木状導出原理の証明サイズについて'',

>> Abstract
id=1999-18

Oblivious BPとSyntactic BPの計算時間による指数的分離'',

>> Abstract
id=1999-20

鳩の巣原理に対する木状導出原理の証明サイズの上下限の改良'',

>> Abstract
id=1999-22

非適応メッシュラウティング'',

(invited talk)
id=1999-24

PVMによるSAT並列局所探索プログラム'',

>> Abstract
id=1999-25

論理回路の最大消費電力問題の近似可能性について'',

>> Abstract
id=1999-26

論理回路の最大消費電力問題に対する近似アルゴリズム'',

id=1999-27

PVMによるSATアルゴリズムの高速化'',

id=1999-28

オンライン独立頂点集合問題に対する一般化されたオンラインアルゴリズムの性能評価'',

id=1999-29

断線したネットワークの復旧問題に対する近似アルゴリズム'',

## [ その他 ]

id=1999-14
D. Manlove, R. Irving, K. Iwama, S. Miyazaki, and Y. Morita,
Hard Variants of Stable Marriage'',
Technical Report of the Computing Science Department, TR-1999-43, Glasgow University, Sep. 1999.

## Abstract

id=1999-01
オンライン金融問題における代表的戦略はいわゆる「脅威原理」に基づくも のである．これは，何時如何なる時点で脅威的な事態が生じても一定の利得を 確保することを保証する戦略で，別の言葉で言えば，最悪の場合の結果を最善 にすることを目的にした保守的で安全な戦略であると言える．これは，オンラ インアルゴリズムの性能評価が競合比（オフラインアルゴリズムの利得との比 の最悪値）で計られることを考えれば自然なことではある．しかし，実際的立 場からは「面白み」に欠けるという指摘があることも確かである．この観点か ら， al-Binali は「ギャンブル性」の導入を提案した．それは， 予測という概念の導入であり，予測が当たればより良い結果が得られるが，外 れても脅威原理に基づく利得に比べて一定の減少のみに留まるというものである．
id=1999-02
Our model in this paper is a 1.5-way quantum finite automaton which can move its head 0 or +1 position but not $-1$ position. It is shown that the most fundamental decision question, the emptiness problem, is not solvable for this model. Note that the emptiness problem is solvable for push-down automata and even for one-way nondeterministic stack automata.
id=1999-03

id=1999-04
Our model in this paper is a 1.5-way quantum finite automaton which can move its head 0 or +1 position but not $-1$ position. It is shown that the most fundamental decision question, the emptiness problem, is not solvable for this model. Note that the emptiness problem is solvable for push-down automata and even for one-way nondeterministic stack automata.
id=1999-05
Mesh routing has long been a popular problem and has a huge literature. However, it is also true that there still remain several important unknowns. In this presentation, we report our recent results on this problem, namely, improved upper bounds based on some new techniques. Especially we focus on the following two major results: (1)~A first optimal up to the constant factor algorithm for oblivious permutation routing on the 2-D mesh computer of constant queue size, and (2)~effcient randomized algorithms on the 2-D mesh of buses. The first result exploits the bit reversal permutation to achieve an average scattering of packets. The second one is a randomized algorithm, but the efficiency is achieved by reducing the degree of randomness, i.e., reducing the number of random numbers to be generated.
id=1999-06

id=1999-07
It is said that a set $L_{1}$ in a class $C_{1}$ is an {\it approximation} of a set $L_{2}$ in a class $C_{2}$ if $L_{1}$ is a subset of $L_{2}$. An approximation $L_{1}$ is said to be {\it optimal} if there is no approximation $L'_{1}$ such that $L_{1} \subset L'_{1}$ and $L'_{1}-L_{1}$ is infinite. When the class $C_{1}$=P and $C_{2}$=NP, it is known that there is no optimal approximation under a quite general condition unless P=NP. In this paper we discuss the case where $C_{1}$=the class of NP-complete sets and $C_{2}$=coNP. A similar result as above that shows the difficulty of the optimal approximation is obtained. Approximating coNP sets by NP-complete sets plays an important role in the efficient generation of test instances for combinatorial algorithms.
id=1999-08
テープ記号数を制限したチューリング機械(TM)を用いて，領域階層定理 を稠密化する．任意の構成可能関数$s_1(n)$に対し，次の条件を満たす言 語$L$が存在することを示す．(i)いかなる決定性TMでも$m$記号$s_1(n)$ 領域では$L$を受理できない．(ii) $L$を受理する$m$記号$s_2(n)$領域の 決定性TMが存在する．ただし， $s_2(n)=s_1(n)+\frac{s_1(n)}{\sqrt{(\frac{2}{3}-\epsilon)n}} +(4+\epsilon_1)\log_ms_1(n)+(3+\epsilon_2)\log_mn$. 従って，$s_1(n)\ne O(\log n)$のとき，$m$記号$(1+o(1))s_1(n)$領域の TMは$m$記号$s_1(n)$領域のTMより能力が高いと言える．
id=1999-09
The original stable marriage problem requires all men and women to submit a complete and strictly ordered preference list. This is obviously often unrealistic 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 permitted 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 the optimal cost version has no approximation algorithm achieving the approximation ratio of $N^{1-\epsilon}$, where $N$ is the instance size, unless P=NP.
id=1999-10
Our model in this paper is the standard, two-dimensional $n\times n$ mesh. The first result is a randomized algorithm for $h$-$h$ routing which runs in $O(hn)$ steps with high probability using queues of constant size. The previous bound is $0.5hn+o(hn)$ but needs the queue-size of $\Omega(h)$. An important merit of this algorithm is to give us improved bounds by applying several schemes of faulty-mesh routing. For example, the scheme by cite{rag95}, originally $O(n\log n)$ time and $O(\log^2 n)$ queue-size, gives us an improved routing algorithm on $p$-faulty meshes ($p\leq 0.4$) which runs in $O(n\frac{\log^2 n}{k})$ time using $O(k)$ queue-size for any $k\leq \log n$. Thus, when $k=\log n$ it improves the queue-size by the factor of $\log n$ without changing the time bound and when $k$ is constant, it needs only constant queue-size although the running time slows down by the factor of $\log n$.
id=1999-11
In this paper, we give two online problems, Online MAX WEIGHTED SAT and Online MAX WEIGHTED INDEPENDENT SET, which are hardest in the following two senses: (i) These problems can simulate all online problems without worsening the competitive ratio at all. (ii) We can show that the lower bound of the competitive ratio for these problems is the worst possible even if we can use probably the most powerful online algorithm (an algorithm which can hold many intermediate solutions simultaneously).
id=1999-12

id=1999-13
El-Yaniv et al. presented an optimal on-line algorithm for the unidirectional currency conversion problem based on the threat-based strategy. Later, al-Binali pointed out that this algorithm, while certainly optimal in terms of the competitive ratio, may be too conservative from gamblers' view points.'' He proposed the trading strategy using the forecast that the rate will increase to at least some level $M_1$. If the forecast is true, the algorithm achieves a better competitive ratio than the ratio $r_0^{\star}$ of the threat-based strategy. Otherwise, the algorithm suffers from a loss (a worse ratio than $r_0^{\star}$) but it can be controlled within a certain factor. In this paper, we generalize this notion of forecasts: (i) Not only the forecast that the rate will increase to some level, called an {\it above-forecast}, but the forecast that the rate will never increase to some level, a {\it below-forecast}, is also allowed. (ii) Forecasts are allowed twice or more. Several different algorithms can be designed using this extension, e.g., an algorithm making two rounds of forecasts where one can regain $r_0^{\star}$ by the second forecast even if the first forecast is known to be false. Another result shows that if below-forecasts are involved, the bidirectional conversion (both from dollar to yen and yen to dollar) helps a lot even for a monotonically-changing rate. Note that the bidirectional conversion does not give us any benefit in the case of the threat-based strategy or using only above-forecasts.
id=1999-15

id=1999-16

id=1999-18

id=1999-19
Our main result shows that a shortest proof size of tree-like resolution for the pigeonhole principle is superpolynomially larger than that of DAG-like resolution. In the proof of a lower bound, we exploit a relationship between tree-like resolution and backtracking, which has long been recognized in this field but not been used before to give explicit results.
id=1999-20

id=1999-21
Given an $n$-vertex graph with nonnegative edge weights and a positive integer $k \leq n$, our goal is to find a $k$-vertex subgraph with the maximum weight. We study the following greedy algorithm for this problem: repeatedly remove a vertex with the minimum weighted-degree in the currently remaining graph, until exactly $k$ vertices are left. We derive tight bounds on the worst case approximation ratio $R$ of this greedy algorithm: $(1/2 + n/2k)^2 - O(n^{-1/3}) \leq R \leq (1/2 + n/2k)^2 + O(1/n)$ for $k$ in the range $n/3 \leq k \leq n$ and $2(n/k - 1) - O(1/k) \leq R \leq 2(n/k - 1) + O(n/k^2)$ for $k < n/3$. For $k = n/2$, for example, these bounds are $9/4 \pm O(1/n)$, improving on naive lower and upper bounds of 2 and 4 respectively. The upper bound for general $k$ compares well with currently the best (and much more complicated) approximation algorithm based on semidefinite programming.
id=1999-23
An optimal $\lceil 1.5N^{1/2}\rceil$ lower bound is shown for oblivious routing on the mesh of buses, a two-dimensional parallel model consisting of $N^{1/2}\times N^{1/2}$ processors, $N^{1/2}$ row and $N^{1/2}$ column buses but no local connections between neighbouring processors. Many lower bound proofs for routing on mesh-structured models use a {\it single} instance (adversary) which includes difficult packet-movement. This approach does not work in our case; our proof is one of the rare cases which really exploit the fact that the routing algorithm has to cope with many different instances. Note that the two-dimensional mesh of buses includes $2N^{1/2}$ buses and each processor can access two different buses. Apparently the three-dimensional model provides more communication facilities, namely, including $3N^{2/3}$ buses and each processor can access three different buses. Surprisingly, however, the oblivious routing on the three-dimensional mesh of buses needs more time, i.e., $\Omega(N^{2/3})$ steps, which is another important result of this paper.
id=1999-24

id=1999-25