岩間研究室 発表論文
2000年度
[ 論文誌 ]
- id=2000-01
- K. Iwama, Y. Kambayashi, and K. Takaki,
- ``Tight Bounds on the Number of States of DFA's That Are Equivalent to n-State NFA's'',
-
Theoretical Computer Science, vol.237, 1-2, pp.485--494, (発表月不明) 2000.
-
-
>> Abstract
- id=2000-02
- K. Iwama, and E. Miyano,
- ``Recent Developments in Mesh Routing Algorithms'',
-
IEICE Transactions on Information and Systems, vol.E83-D, no.3, pp.530--540, Apr. 2000.
-
-
>> Abstract
- id=2000-21
- K. Yoda, Y. Okabe, and M. Kanazawa,
- ``An Unbiased Global Coin Flipping Protocol on Synchronous Distributed Systems'',
-
IEICE Transactions on Information and Systems, vol.E84, Jan. 2001.
-
-
>> Abstract
[ 国際会議 ]
- id=2000-09
- K. Iwama, and E. Miyano,
- ``A $(2.954 + \epsilon)n$ Oblivious Routing Algorithm on 2D Meshes'',
-
Proc. ACM SPAA 2000, pp.186--195, Jul. 2000.
-
-
>> Abstract
- id=2000-10
- K. Iwama, and A. Kawachi,
- ``Brief Announcement: Compact Routing with Stretch Factor of Less Than Three'',
-
Proc. ACM PODC 2000, pp.337, Jul. 2000.
- id=2000-11
- M. Halld\'orsson, K. Iwama, S. Miyazaki, and S. Taketomi,
- ``Online Independent Sets'',
-
Proc. COCOON 2000, LNCS 1858, pp.202--209, Jul. 2000.
-
-
>> Abstract
- id=2000-12
- K. Iwama, A. Matsuura, and M. Paterson,
- ``A Family of NFA's which Need $2^n-\alpha$ Deterministic States'',
-
Proc. MFCS 2000, LNCS 1893, pp.436--445, Aug. 2000.
-
-
>> Abstract
- id=2000-13
- K. Iwama, D. Kawai, S. Miyazaki, Y. Okabe, and J. Umemoto,
- ``Parallelizing Local Search for CNF Satisfiability Using Vectorization and PVM'',
-
Proc. WAE 2000, Sep. 2000.
-
-
>> Abstract
- id=2000-15
- E. Yokoyama, K. Yasuoka, Y. Okabe, and M. Kanazawa,
- ``Implementation of a Fast Integer Sorting Library on VPP Parallel Vector Supercomputer'',
-
Proc. The 4th Annual HPF User Group Meeting (HUG 2000), pp.45--50, Oct. 2000.
-
-
>> Abstract
- id=2000-18
- K. Iwama, and A. Kawachi,
- ``Compact routing with stretch factor of less than three'',
-
Proc. IASTED PDCS2000, pp.223--228, Nov. 2000.
-
-
>> Abstract
- id=2000-19
- K. Iwama, and E. Miyano,
- ``Towards an Optimal Oblivious Routing Algorithms on 2D Meshes'',
-
Proc. Workshop on Algorithm Engineering as a New Paradigm, pp.253--262, Nov. 2000.
- id=2000-20
- T. Asano, M. Halld\'orsson, K. Iwama, and T. Matsuda,
- ``Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits'',
-
Proc. ISAAC 2000, LNCS 1969, pp.204--215, Dec. 2000.
-
-
>> Abstract
[ 国内発表 ]
- id=2000-03
- 盛田保文, 宮崎修一, 岩間一雄, M. Halld\'orsson,
- ``安定結婚問題の近似可能性について'',
- 京都大学数理解析研究所講究録, 1148 (計算機科学の基礎理論：21世紀の計算パラダイムを目指して), pp.124--129, 2000年 4月.
-
-
>> Abstract
- id=2000-04
- 河内亮周, 岩間一雄,
- ``伸長係数2のコンパクトラウティングアルゴリズム'',
- 京都大学数理解析研究所講究録, 1148 (計算機科学の基礎理論：21世紀の計算パラダイムを目指して), pp.219--224, 2000年 4月.
-
-
>> Abstract
- id=2000-05
- 武富史郎, 宮崎修一, 岩間一雄, M. Halld\'orsson,
- ``一般化されたオンライン独立頂点集合問題の競合比'',
- 電子情報通信学会 コンピュテーション研究会, 信学技報, COMP2000-4, pp.25--32, 2000年 4月.
-
-
>> Abstract
- id=2000-06
- 岩間一雄,
- ``CNF充足可能性問題の現実的解法'',
- 情報処理学会 アルゴリズム研究会, 情処研報, vol.2000, no.41, pp.1, 2000年 5月.
-
- (invited talk)
- id=2000-07
- 宮野英次, 岩間一雄,
- ``メッシュ上での高速な無情報ラウティングアルゴリズム'',
- 情報処理学会 アルゴリズム研究会, 情処研報, vol.2000, no.41, pp.11--18, 2000年 5月.
- id=2000-08
- 河合大輔, 宮崎修一, 岡部寿男, 岩間一雄,
- ``SATに対する局所探索法のベクトル化'',
- 情報処理学会並列処理シンポジウム (JSPP2000) 論文集, pp.43--50, 2000年 5月.
-
-
>> Abstract
- id=2000-14
- 吉廣卓哉, 岡部寿男, 岩間一雄,
- ``DiffServフレームワークにおける適応ルーティングによる低優先度通信の迂回'',
- 第3回インターネットテクノロジーワークショップ (WIT2000), 2000年 9月.
-
-
>> Abstract
- id=2000-16
- 松浦昭洋, 岩間一雄, M. Paterson,
- ``$2^n-\alpha$個の決定性状態を要する$n$状態NFAの族について'',
- 電子情報通信学会 コンピュテーション研究会, 信学技法, vol.100, no.402, COMP2000-44, pp.17--24, 2000年 10月.
-
-
>> Abstract
- id=2000-17
- 岩間一雄,
- ``量子計算と量子アルゴリズム'',
- 電子情報通信学会 情報理論研究会, 第23回情報理論とその応用シンポジウム, IT2000-34, 2000年 10月.
-
- (invited talk)
- id=2000-22
- 藤原洋志, 岩間一雄,
- ``レンタルスキー問題に対する平均的競合比の解析'',
- 情報処理学会 アルゴリズム研究会, 情処研報, vol.2001, no.7, pp.43--50, 2001年 1月.
-
-
>> Abstract
- id=2000-23
- 島田将行, 吉廣卓哉, 岡部寿男, 岩間一雄,
- ``IPv6におけるサイトローカルアドレスの自動設定'',
- 分散システム／インターネット運用技術シンポジウム 2001, 2001年 2月.
-
-
>> Abstract
- id=2000-24
- 関口隆昭, 藤川賢治, 岡部寿男, 岩間一雄,
- ``QoS保証マルチキャストプロトコルSRSVPにおける階層化PathQoS'',
- 第102回 マルチメディア通信と分散処理研究会 (DPS研究会), 2001年 3月.
- id=2000-26
- 玉置卓, 岩間一雄,
- ``偏りのある充足解をもつSATに対する局所探索アルゴリズムの解析と応用'',
- 2001年電子情報通信学会総合大会講演論文集, D-1-3, 2001年 3月.
- id=2000-27
- 宮武和史, 宮崎修一, 岩間一雄,
- ``最大化および最小化アルゴリズムにおける近似度の関係'',
- 2001年電子情報通信学会総合大会講演論文集, D-1-4, 2001年 3月.
- id=2000-28
- Rudy Raymond H.P., 岩間一雄,
- ``量子有限オートマトンのシミュレーションシステム'',
- 2001年電子情報通信学会総合大会講演論文集, D-1-5, 2001年 3月.
[ 解説 ]
- id=2000-25
- 岩間一雄,
- ``乱数を利用した証明'',
- Computer Today, (特集アルゴリズムの新展開：理論から工学へ), vol.18, no.2, pp.6--12, 2001年 3月.
Abstract
-
id=2000-01
- It is shown that if $\alpha$ is an integer which can be expressed as
$2^k$ or $2^k+1$ for some integer $0 \leq k \leq n/2 -2$, then there
exist nondeterministic finite automata with $n$ states whose
equivalent deterministic finite automata need exactly $2^n -\alpha$
states.
-
id=2000-02
- メッシュ結合計算機モデルおよびメッシュバス計算機モデル上でのラウティ
ングに関して，最近得られたラウティングテクニックおよびラウティング時間
をまとめたサーベイ論文である．メッシュラウティングにおける決定性アルゴ
リズム，確率的アルゴリズム，文献の紹介を行い，本研究分野の今後の研究課
題について述べている．
-
id=2000-03
- 安定結婚問題の入力例題のリストに同順位と不完全性を許した場合、最大の
安定マッチングを求める問題はNP困難であることが知られている。本稿では、
この問題の近似可能性について論じ、P$\neq$NPの仮定のもとで、この問題が
PTASを持たないことを示した。また、一般の例題および制限された例題に対す
る近似可能性を論じ、自明な近似度2からの改善された結果を示した。
-
id=2000-04
- Cowenによって単純で実際的なモデルの下で伸長係数$3$、テーブルサイズ
$O(n^{2/3}\log^{4/3}n)$のコンパクトラウティングアルゴリズムが示された。
本稿では同じモデルを用いて伸長係数が$3$未満の場合に必要なテーブルサイ
ズがどの程度大きくなるかを調べ、その結果、(i)~伸長係数$2$で各節点のテー
ブルサイズの上限$(n-\sqrt{n}+2)\log n$のアルゴリズムの存在、(ii)~伸長
係数$3$未満のどんなアルゴリズムに対しても$(n-2\sqrt{n})\log n$のテーブ
ルサイズが必要となる節点を持つグラフの存在、が示される。テーブルサイズ
$n\log n$で自明に最短距離を保証するラウティングが可能であるから、それ
に比べて$\sqrt{n}\log n$程度しか減らすことができない。
-
id=2000-05
- オンライン独立頂点集合問題とは各時点で1つの頂点$v_i$と, $v_i$に接続す
る枝が与えられ, その頂点を独立頂点集合に入れるか否かを決定し, 最終的に
できるだけ大きなサイズの独立頂点集合を得ることを目的とする問題であ
る. 従来の設定のように解を1つしか持つことを許さないモデルを用いた場合
には，グラフの総頂点数を$n$として，競合比の上下限は$n-1$となる．本研究
では同時に多項式個の解を保持することを許したモデルを2つ考案し, それぞ
れの競合比の上限と下限を与えた.
-
id=2000-08
- 本研究の目的は，論理式の充足可能性問題(SAT)の解法アルゴリズムである局
所探索法の高速化である．局所探索法のアルゴリズムGSATに対し，実働化時の
工夫と並列化によって高速化を試みる．SelmanとKautzのGSATを元に，(i)~デー
タ構造の改良，(ii)~ベクトル並列計算機上でのベクトル化，(iii)~PVMを使っ
た40CPUによる並列化，を行った．これにより，合計600倍の高速化を達成した．
2nd DIMACS Implementation Challenge, Satisfiability のベンチマーク例題
に対して我々のGSATを実行させたところ，既存のプログラムで解けている例題
では実行時間がかなり短縮された．また，GSATを改良した局所探索法に本論文
の手法を適用させることにより，既存のプログラムでは解けなかった例題を解
くまでに至った．
-
id=2000-09
- $n\times n$個のプロセッサを持ち，キューサイズが定数であるような2次元
メッシュ結合計算機モデル上でのラウティング問題について論じている．本論
文では，決定性，無情報，1対1ラウティング問題に対して，$(2.954 +
\varepsilon)n$時間($\varepsilon$は任意の正定数)のアルゴリズムを示して
いる．これまでの計算時間の定数係数は少なくとも$1000$以上であり，その値
を約$3$まで小さくできることを示している．
-
id=2000-11
- At each step of the online independent set problem, we are given a
vertex $v$ and its edges to the previously given vertices. We are to
decide whether or not to select $v$ as a member of an independent set.
Our goal is to maximize the size of the independent set. It is not
difficult to see that no online algorithm can attain a performance
ratio better than $n-1$, where $n$ denotes the total number of
vertices. Given this extreme difficulty of the problem, we study here
relaxations where the algorithm can hedge his bets by maintaining
multiple alternative solutions simultaneously.
We introduce two models. In the first, the algorithm can maintain a
polynomial number of solutions (independent sets) and choose the
largest one as the final solution. We show that $\theta(\frac{n}{\log
n})$ is the best competitive ratio for this model. In the second more
powerful model, the algorithm can copy intermediate solutions and grow
the copied solutions in different ways. We obtain an upper bound of
$O(n/(k\log n))$, and a lower bound of $n/(e^{k+1} \log^3 n)$, when
the algorithm can make $n^k$ operations per vertex.
-
id=2000-12
- We show that for all integer $n \ge 7$ and $\alpha$, such that $5 \le
\alpha \le 2n-2$ and satisfying some coprimality conditions, there
exists a minimum $n$-state nondeterministic finite automaton that is
equivalent to a minimum deterministic finite automaton with exactly
$2^n - \alpha$ states.
-
id=2000-13
- The purpose of this paper is to speed up the local search algorithm
for the CNF Satisfiability problem. Our basic strategy is to run some
$10^{5}$ independent search paths simultaneously using PVM on a vector
supercomputer VPP800, which consists of 40 vector processors. Using
the above parallelization and vectorization together with some
improvement of data structure, we obtained 600-times speedup in terms
of the number of flips the local search can make per second compared
to the original GSAT by Selman and Kautz. We run our parallel GSAT
for benchmark instances and compared the running time with those of
existing SAT programs. We could observe an apparent benefit of
parallelization: Especially, we were able to solve two instances that
have never been solved before this paper. We also tested parallel
local search for the SAT encoding of the class scheduling problem.
Again we were able to get almost the best answer in reasonable time.
-
id=2000-14
- インターネットでQoS保証を行う枠組みの一つとして, DiffServが研究されて
いる. DiffServは, ドメイン内でパケットを複数クラスに分類し差別化を行う
が, キューイングのみによるため, 高優先度通信の保護が低優先度通信の品質
劣化につながるという必然的な限界を持つ. 本研究では, DiffServの低優先度
クラスに対してOSPFのコスト値操作を行い, 適応的に輻輳を迂回することでよ
り効率的なネットワーク利用を行う方式を提案する. この方式では, コスト変
更時に一時的な経路ループのないアルゴリズムを考案することで, 適応ルーティ
ングを可能にしている. また, この提案に基づきシステムの設計, 実装を行っ
ている.
-
id=2000-15
- We propose a fast sorting algorithm for VPP distributed-memory
parallel vector supercomputers. Our algorithm is based on the bucket
sort, and utilizes the RETRY algorithm~[Murai, Suehiro, Seo:
Trans. IPSJ 39-6, 1595-1602] as the local sorting algorithm on each
vector processor.
Bucket sort is parallelized as follows. First each processor computes
the local histogram. Next the local histograms are redistributed.
Then the processors compute the global histogram in parallel, and get
the total rank for each key. We have implemented a library code on
Fujitsu VPP 800, and have evaluated its performance on NAS Parallel
Benchmark Integer Sort scheme.
-
id=2000-16
- 本稿では，$n \ge 7$，$5 \le \alpha \le 2n-2$とある素性条件
(coprimality condition)を満たす全ての整数$n$と$\alpha$に対して，$n$状
態非決定性有限オートマトンで，それと同値かつ極小な決定性有限オートマト
ンの状態数がちょうど$2^n-\alpha$であるものが存在することを示す．
-
id=2000-18
- Recently, Cowen gave a universal compact routing algorithm with a
stretch factor of three and table-size of $O(n^{2/3}\log^{4/3}n)$
based on a simple and practical model. This paper considers, using the
same model, how the necessary table-size differs if the stretch factor
must be {\it less than} three. It is shown that: (i)~There is a
routing algorithm with a stretch factor of two whose table-size is
$(n-\sqrt{n}+2)\log n$. (ii)~There is a network for which any routing
algorithm that follows the model and with a stretch factor of less
than three needs a table-size of $(n-2\sqrt{n})\log n$ in at least one
node. Thus, we can only reduce roughly an {\it additive} $\sqrt{n}\log
n$ (i.e., $\sqrt{n}$ table-entries) from the trivial table-size of
$n\log n$ which obviously enables shortest-path routing. Furthermore
it turns out that we can reduce only an additive $\log n$ (i.e., only
one table-entry) from the trivial $n\log n$ if we have to achieve a
stretch factor of less than {\it two}. Thus the algorithm (i) is
(roughly) tight both in its stretch factor and in its table-size.
-
id=2000-20
- The maximum power consumption problem on combinatorial circuits is
the problem of estimating the maximum power consumption of a given
combinatorial circuit. It is easy to see that this problem for
general circuits is hard to approximate within a factor of $m^{1 -
\epsilon}$, where $m$ is the number of gates in an input circuit and
$\epsilon$ is any positive (small) constant. In this paper, we
consider restricted circuits, namely, those consisting of only one
level of AND/OR gates. Then the problem becomes a kind of MAX 2SAT
where each variable takes one of four values, $f$, $t$, $d$ and $u$.
This problem is NP-hard and the main objective of this paper is to
give approximation algorithms.
We consider two cases, the case that positive and negative appearances
of each variable are well balanced and the general case. For the
first case, we achieve an approximation ratio of ${2(3k - \ell)\over
\alpha (3k + \ell)}$ where $\alpha = 0.87856$ and $k \over \ell$ is
the maximum ratio of the number of positive appearances over the
number of negative appearances of each variable. For the general
case, we obtain an approximation ratio of 1.7. Both results involve
deep, systematic analyses.
-
id=2000-21
- We present a distributed protocol for achieving totally unbiased
global coin flipping in the presence of an adversary. We consider a
synchronous system of $n$ processors at most $t$ of which may be
corrupted and manipulated by a malicious adversary, and assume a
complete network where every two processors are connected via a
private channel.
Our protocol is deterministic and assumes a very powerful adversary.
Although the adversary cannot eavesdrop, it is computationally
unbounded, capable of rushing and dynamic. This is the same model
that is adopted in Yao's global coin flipping protocol, which we use
as the base of our protocol. Our protocol tolerates almost $n/3$
processor failures and terminates in $t+4$ rounds. The resilience of
our protocol is greatly improved from that of Yao's protocol at the
slight expense of running time, which is only added just two rounds.
-
id=2000-22
- オンライン問題における競合比の解析は，通常最悪の場合に対して行われて
いる．本稿では我々はレンタルスキー問題に対して平均の場合の解析を試みる．
つまり，スキーに行く回数に指数分布を仮定したモデルを考え，平均的競合比
を定義しこれについて考察を進める．そして結果としてこの考察における最適
解が，最悪の場合に対してのオンラインアルゴリズムの最適解とかなり異なっ
てくることを示す。
-
id=2000-23
- IPv6のサイトローカルアドレスを無設定(zeroconf)でステートレスに自動割
り当てする枠組を提案する。当該セグメントに最初に接続されたルータが、そ
のセグメントのリーダとなって、16bitのsubnet ID部分をランダムに選んだプ
レフィックスを生成する。アドレスのサイト内での一意性を保証するために、
RIPngを拡張したプレフィックスアドレス重複の検出方法を示す。重複が検出
されると直ちにセグメントリーダへ通知され、IPv6のアドレス付替の仕組を用
いて新たなアドレスへの付替が行われる。