岩間研究室発表論文

1999年度

[ 論文誌 ]

id=1999-06: 農添三資, 浜口清治, 岩間一雄, 矢島脩三,; ``しきい値関数を表す共有2分決定グラフの最適な変数順序付けの計算複雑度'',; 電子情報通信学会論文誌, vol.J82-D-I, no.5, pp.595--602, 1999年 6月.; >> 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: 岩本宙造, 岩間一雄,; ``テープ記号数を制限したチューリング機械の領域階層'',; 電子情報通信学会論文誌, vol.J82-D-I, no.6, pp.661--668, 1999年 6月.; >> 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: 米澤弘毅, 岩間一雄,; ``一方向通貨交換問題における予測を用いたアルゴリズム'',; 京都大学数理解析研究所講究録, 1093 (計算モデルとアルゴリズム), pp.15--20, 1999年 4月.; >> Abstract

id=1999-02: 天野正己, 岩間一雄,; ``量子有限オートマトンにおける決定不能問題'',; 京都大学数理解析研究所講究録, 1093 (計算モデルとアルゴリズム), pp.200--205, 1999年 4月.; >> Abstract

id=1999-03: 内田敦, 宮崎修一, 岩間一雄,; ``オンライン問題の複雑さの解析について'',; 電子情報通信学会コンピュテーション研究会, 信学技法, vol.99, no.30, COMP99-8, pp.57--64, 1999年 4月.; >> Abstract

id=1999-12: 高瀬俊郎, 岡部寿男, 岩間一雄,; ``Syntactic BP と oblivious BP の分離'',; 1999年夏のLAシンポジウム予稿 (LAシンポジウム), 1999年 7月.; >> Abstract

id=1999-15: 宮野英次, 岩間一雄,; ``メッシュ上でのビット反転置換を用いたラウティングアルゴリズム'',; 情報処理学会アルゴリズム研究会, 情処研報, vol.99, no.72, pp.17--24, 1999年 9月.; >> Abstract

id=1999-16: 宮崎修一, 岩間一雄,; ``鳩の巣原理に対する木状導出原理の証明サイズについて'',; 電子情報通信学会コンピュテーション研究会, 信学技法, vol.99, no.288, COMP99-33, pp.15--22, 1999年 9月.; >> Abstract

id=1999-18: 高瀬俊郎, 岡部寿男, 岩間一雄,; ``Oblivious BPとSyntactic BPの計算時間による指数的分離'',; 電子情報通信学会コンピュテーション研究会, 信学技法, vol.99, no.432, COMP99-50, pp.9--15, 1999年 11月.; >> Abstract

id=1999-20: 宮崎修一, 岩間一雄,; ``鳩の巣原理に対する木状導出原理の証明サイズの上下限の改良'',; 京都大学数理解析研究所講究録, 1120 (新しいパラダイムとしてのアルゴリズム工学), pp.51--57, 1999年 12月.; >> Abstract

id=1999-22: 岩間一雄,; ``非適応メッシュラウティング'',; 日本OR学会関西支部組合せ最適化研究部会, 2000年 1月.; (invited talk)

id=1999-24: 梅本潤, 宮崎修一, 岡部寿男, 岩間一雄,; ``PVMによるSAT並列局所探索プログラム'',; 情報処理学会計算機アーキテクチャ研究会・ハイパフォーマンスコンピューティング研究会, 情処研報, vol.2000, no.23, pp.95--100, 2000年 3月.; >> Abstract

id=1999-25: 松田健, 岩間一雄, M. Halld\'orsson,; ``論理回路の最大消費電力問題の近似可能性について'',; 情報処理学会アルゴリズム研究会, 情処研報, vol.2000, no.31, pp.9--16, 2000年 3月.; >> Abstract

id=1999-26: 松田健, 岩間一雄,; ``論理回路の最大消費電力問題に対する近似アルゴリズム'',; 第60回(平成12年後期)情処全国大会講演論文集, vol.1, pp.173--174, 2000年 3月.

id=1999-27: 梅本潤, 宮崎修一, 岡部寿男, 岩間一雄,; ``PVMによるSATアルゴリズムの高速化'',; 第60回(平成12年後期)情処全国大会講演論文集, vol.1, pp.177--178, 2000年 3月.

id=1999-28: 武富史郎, 宮崎修一, 岩間一雄, M. Halld\'orsson,; ``オンライン独立頂点集合問題に対する一般化されたオンラインアルゴリズムの性能評価'',; 第60回(平成12年後期)情処全国大会講演論文集, vol.1, pp.193--194, 2000年 3月.

id=1999-29: 西村知洋, 宮崎修一, 岩間一雄,; ``断線したネットワークの復旧問題に対する近似アルゴリズム'',; 第60回(平成12年後期)情処全国大会講演論文集, vol.1, pp.199--200, 2000年 3月.

[ その他 ]

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: 本稿ではOnline MWSAT, Online MWISという2つのオンライン問題を導入し，これらの問題が以下の2つの意味で最も困難なオンライン問題であることを示す．(i) これらの問題は，任意のオンライン問題を模倣可能である．(ii) これらの問題は，より強力なオンラインアルゴリズム（複数の解を同時に保持することを許されたオンラインアルゴリズム）によっても，最悪の競合比しか得られない．証明には，NP最適化問題の完全性の証明を利用した．即ち，オンライン問題を非決定性チューリング機械で定式化し，それをOnline MWSATが模倣可能であることを示した．

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: 論理関数の表現である共有2分決定グラフは，論理回路の計算機援用設計の様々な分野で利用されている．共有2分決定グラフは，与える論理変数の順序によって，その大きさが変化するが，共有2分決定グラフの最適化問題，すなわち，大きさが与えられた定数 $k$ 以下になる変数順序が存在するかという問題については，すでに NP 完全であることが知られている．本論文では，共有2分決定グラフを，しきい値関数のみを表現するもののみに制限した場合でも，最適化問題がやはり，NP完全となることを示す．

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: 我々は単純な論理関数を与える. この関数はsyntactic 1回読み分岐プログラムで多項式サイズで計算可能であるが, oblivious $k$回読み分岐プログラムでは$k>0$である$k$に対して多項式サイズでは計算不可能である.

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: 本稿では，2次元，定数サイズキュー，$n\times n$メッシュ計算機上でのラウティング問題に対する$(3+\varepsilon)n$時間の決定性無情報ラウティングアルゴリズムを示す．SODA99において，我々は，$O(n)$時間の無情報ラウティングアルゴリズムが存在することを示していた．しかし，定数係数の具体的な値は示しておらず，その値は明らかに1000以上になっていた．

id=1999-16: 鳩の巣原理に対する木状導出原理の証明サイズの上下限の改良を行なう．上下限の改良という本来の結果の他に，木状導出原理による証明サイズが一般の導出原理に対するものよりも超多項式的に大きい例を，最も研究のなされている鳩の巣原理に対しても示した．下限の証明には，木状導出原理とSATアルゴリズムであるバックトラック法との等価性を利用した．

id=1999-18: 次のようなOblivious BP(oBP)とSyntactic BP(sBP)の計算時間による指数的分離を示した. (i)次のような入力長$N$である関数$f_2$が存在する. $f_2$は多項式サイズoBPで長さ$\Omega (N\log N)$必要であるが, 多項式サイズ1回読みsBPで長さ$O(\log^3 N)$で計算可能である. (ii)次のような入力長$N$である関数$f_k$が存在する. $f_k$は多項式サイズoBPで長さ$\Omega (N\log^2 N)$必要であるが, 多項式サイズ2回読みsBPで長さ$O(N^{\varepsilon })$で計算可能である.

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: 鳩の巣原理に対する木状導出原理の証明サイズの上下限の改良を行なう．上限は従来の$O(n^{3} n!)$を$O(n^{2} n!)$に，下限は従来の $2^{n}$を$(\frac{n}{4\log^{2} n})^{n}$に改良する．本結果により，鳩の巣原理に対する木状導出原理の証明サイズが一般の導出原理の証明サイズの多項式では抑えられないことが導かれる．下限の証明には，バックトラック法と木状導出原理の関係を利用するという，これまでにない新たな手法を用いた．

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: 充足可能性問題(SAT)は基本的な組み合わせ問題である. 高速なSATの解法アルゴリズムとして局所探索法があるが, 大規模な問題にも対応するため更なる高速化の重要性が高まっている. そこで, 本稿では局所探索法をネットワーク並列計算用ソフトウェアシステムであるPVM(Parallel Virtual Machine)で並列化して実行する高速化手法を提案する. 局所探索法のTRYという実行単位を各計算機で並列に実行するTRY同時実行により, 効率的に高速化できることを示した. さらに, 2nd DIMACS Implementation Challengeのsatisfiabilityのベンチマークに対して計算機実験を行い, これまで解かれていなかった例題をワークステーション70台を用いて8,500秒程で解くことができた.

id=1999-25: 論理回路の最大消費電力問題とは、与えられた論理回路に対して、その消費電力を最大化する入力値のペアを求める問題である。一般の回路の場合には、この問題に対する近似度$m^{1 - \epsilon}$以下のアルゴリズムは存在しないことを示した。そこで、我々の研究では対象とする回路をAND一段のみの回路に制限する。この制限のもとでの最大消費電力問題を{\bf 0}、{\bf 1}、{\bf u}、{\bf d}の4値を使用する式の最大充足化問題として定式化した。まず、この問題がNP困難であることを証明する。次に、近似アルゴリズムとして、変数の肯定・否定がバランスよく現れる場合には比較的よい近似度が得られることを示す。一般の場合に対する近似度1.98のアルゴリズムも与える。

岩間研究室 発表論文

1999年度

[ 論文誌 ]

[ 国際会議 ]

[ 国内発表 ]

[ その他 ]

Abstract

岩間研究室発表論文