岩間研究室発表論文

2002年度

[ 論文誌 ]

id=2002-03: D. Manlove, R. Irving, K. Iwama, S. Miyazaki, and Y. Morita,; ``Hard Variants of Stable Marriage'',; Theoretical Computer Science, vol.276, 1-2, pp.261--279, Apr. 2002.

id=2002-04: A. Uejima, and H. Ito,; ``On $H$-coloring Problems with $H$ Expressed by Complements of Cycles, Bipartite Graphs, and Chordal Graphs'',; IEICE Trans., vol.E85-A, no.5, pp.1026--1030, May 2002.; >> Abstract

id=2002-08: 吉廣卓哉, 島田将行, 岡部寿男, 岩間一雄,; ``IPv6におけるサイトローカルアドレスのステートレス自動設定'',; システム制御情報学会論文誌, vol.15, no.6, pp.294--301, 2002年 6月.; >> Abstract

id=2002-23: H. Ito, M. Ito, Y. Itatsu, K. Nakai, H. Uehara, and M. Yokoyama,; ``Source location problems considering vertex-connectivity and edge-connectivity simultaneously'',; Networks, vol.40, no.2, pp.63--70, Sep. 2002.; >> Abstract

id=2002-34: Y. Asahiro, R. Hassin, and K. Iwama,; ``Complexity of Finding Dense Subgraphs'',; Discrete Applied Mathematics, vol.121, 1-3, Sep. 2002.

id=2002-35: K. Iwama, D. Kawai, S. Miyazaki, Y. Okabe, and J. Umemoto,; ``Parallelizing Local Search for CNF Satisfiability Using Vectorization and PVM'',; ACM Journal of Experimental Algorithmics, vol.7, Sep. 2002.; >> Abstract

id=2002-37: K. Iwama, and S. Yamashita,; ``A Complete Set of Transformation Rules for Quantum Boolean Circuits with CNOT gates'',; Worshop on Quantum Dots for Quantum Computing and Classical Size Effect Circuits (special volume of Superlattices and Microstructures), vol.31, 2-4, pp.181--192, Oct. 2002.; >> Abstract

id=2002-39: M. Halld\'orsson, K. Iwama, S. Miyazaki, and S. Taketomi,; ``Online Independent Sets'',; Theoretical Computer Science, vol.289, no.2, pp.953--962, Oct. 2002.; >> Abstract

id=2002-48: S. Kimura, A. Ishii, T. Horiyama, M. Nakanishi, H. Kajihara, and K. Watanabe,; ``Look Up Table Compaction Based on Folding of Logic Functions'',; IEICE Trans. Fundamentals, vol.E85-A, no.12, pp.2701--2707, Dec. 2002.

id=2002-51: H. Ito,; ``Sum of edge lengths of a multigraph drawn on a convex polygon'',; Computational Geometry, vol.24, no.1, pp.41--47, Jan. 2003.; >> Abstract

id=2002-56: K. Iwama, and A. Matsuura,; ``Solving SAT efficiently with promises'',; IEICE Transactions on Information and Systems, vol.E86-D, no.2, Feb. 2003.; >> Abstract

id=2002-57: T. Horiyama, and T. Ibaraki,; ``Translation among CNFs, Characteristic Models and Ordered Binary Decision Diagrams'',; Information Processing Letters, vol.85, no.4, pp.191--198, Feb. 2003.

[ 国際会議 ]

id=2002-01: M. Halld\'orsson, K. Iwama, S. Miyazaki, and Y. Morita,; ``Inapproximability results on stable marriage problems'',; Proc. Latin American Theoretical INformatics (LATIN 2002), LNCS 2286, pp.554--568, Apr. 2002.; >> Abstract

id=2002-05: K. Iwama, and A. Matsuura,; ``Inclusion-Exclusion for $k$-CNF Formulas'',; Proc. International Symposium on the Theory and Applications of Satisfiability Testing (SAT 2002), pp.182--189, May 2002.; >> Abstract

id=2002-09: T. Yoshihiro, H. Ito, Y. Okabe, and K. Iwama,; ``Avoiding Routing Loops on the Internet'',; Proc. the 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2002), pp.197--210, Jun. 2002.; >> Abstract

id=2002-10: K. Iwama, Y. Kambayashi, and S. Yamashita,; ``Transformation Rules for Designing CNOT-based Quantum Circuits'',; Proc. Design Automation Conference 2002, pp.419--424, Jun. 2002.; >> Abstract

id=2002-12: K. Iwama, and S. Taketomi,; ``Removable On-Line Knapsack Problems'',; Proc. 29th International Colloquium on Automata, Languages and Programming (ICALP'02), LNCS 2380, pp.293--305, Jul. 2002.; >> Abstract

id=2002-13: K. Iwama, and M. Okita,; ``Compact Routing for Average-Case Networks'',; Proc. Principles of Distributed Computing (PODC 2002), pp.255, Jul. 2002.; >> Abstract

id=2002-19: K. Iwama, and H. Morizumi,; ``An Explicit Lower Bound of $5n - o(n)$ for Boolean Circuits'',; Proc. 27th International Symposium on Mathematical Foundations of Computer Science (MFCS 2002), LNCS 2420, pp.353--364, Aug. 2002.; >> Abstract

id=2002-21: K. Iwama,; ``Equivalence problems for finite automata'',; Pre-COCOON Workshop, Aug. 2002.

id=2002-24: K. Iwama, Rudy Raymond H.P., S. Yamashita, and T. Yamakami,; ``Quantum complexity of noisy IP query'',; Workshop on ERATO Quantum Information Science 2002, pp.77--78, Sep. 2002.; >> Abstract

id=2002-25: K. Iwama, A. Kawachi, H. Masuda, Rudy Raymond H.P., and S. Yamashita,; ``Quantum query complexity and the number of inverted states'',; Workshop on ERATO Quantum Information Science 2002, pp.79--80, Sep. 2002.; >> Abstract

id=2002-33: H. Ito,; ``Recent Development of Source Location Problems'',; Proc. the Second Japanese-Sino Optimization Meeting (JSOM 2002), pp.72, Sep. 2002.; >> Abstract

id=2002-36: M. Amano, K. Iwama, and Rudy Raymond H.P.,; ``Exploiting the Difference in Probability Calculation between Quantum and Probabilistic Computations'',; Proc. Unconventional Models of Computation (UMC 2002), LNCS 2509, pp.100--114, Oct. 2002.; >> Abstract

id=2002-40: T. Yoshihiro, M. Shimada, Y. Okabe, and K. Iwama,; ``Stateless Autoconfiguration of IPv6 Site-local Address'',; Proc. IASTED International Communications and Computer Networks (CCN 2002), pp.299--304, Nov. 2002.; >> Abstract

id=2002-41: H. Ito, H. Nagamochi, Y. Sugiyama, and M. Fujita,; ``File Transfer Tree Problems'',; Proc. the 13th Annual International Symposium on Algorithms and Computation (ISAAC2002), LNCS 2518, pp.441--452, Nov. 2002.; >> Abstract

id=2002-42: H. Fujiwara, and K. Iwama,; ``Average-Case Competitive Analyses for Ski-Rental Problems'',; Proc. the 13th Annual International Symposium on Algorithms and Computation (ISAAC 2002), LNCS 2518, pp.476--488, Nov. 2002.; >> Abstract

id=2002-43: S. Kimura, T. Horiyama, M. Nakanishi, and H. Kajihara,; ``Folding of Logic Functions and Its Application to Look Up Table Compaction'',; Proc. of the IEEE/ACM International Conference on Computer Aided Design (ICCAD 2002), pp.694--697, Nov. 2002.

id=2002-49: H. Ito, and H. Nagamochi,; ``Comparing Hypergraphs by Areas of Hyperedges Drawn on a Convex Polygon'',; Proc. the Japan Conference on Discrete and Computational Geometry (JCDCG2002), LNCS 2866, pp.176--181, Dec. 2002.; >> Abstract

id=2002-52: H. Ito, and H. Nagamochi,; ``Can a Hypergraph Cover Every Convex Polygon?'',; Proc. the 3rd Hungarian-Japanese Symposium 2003, pp.293--302, Jan. 2003.; >> Abstract

id=2002-59: S. Kimura, T. Hayakawa, T. Horiyama, M. Nakanishi, and K. Watanabe,; ``An On-Chip High Speed Serial Communication Method Based on Independent Ring Oscillators'',; Proc. International Solid State Circuit Conference (ISSCC 2003), no.22.3, pp.390--391, Feb. 2003.

[ 国内発表 ]

id=2002-02: 岩間一雄, 森住大樹,; ``回路計算量の$5n$の下限'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.102, no.31, COMP2002-1, pp.1--8, 2002年 4月.

id=2002-06: K. Iwama, Rudy Raymond H.P., S. Yamashita, and T. Yamakami,; ``Quantum complexity of noisy IP query'',; 電子情報通信学会第6回量子情報技術研究会, QIT2002-40, pp.191--194, May 2002.; >> Abstract

id=2002-07: 沖田正樹, 岩間一雄,; ``平坦なグラフに対するコンパクトルーティング'',; 情報処理学会アルゴリズム研究会, 情処研報, 2002-AL-84-9, pp.59--66, 2002年 5月.; >> Abstract

id=2002-11: 吉廣卓哉, 伊藤大雄, 岡部寿男, 岩間一雄,; ``インターネットにおける経路ループの回避手法'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.102, no.140, COMP2002-18, pp.25--32, 2002年 6月.; >> Abstract

id=2002-14: 佐久間俊慎, 小野廣隆, 山下雅史, 朝廣雄一, 牧野和久, 堀山貴史,; ``直線軌道移動するロボットによるボール回収問題'',; 夏のLAシンポジウム, 2002年 7月.

id=2002-15: 今村友和, 岩間一雄,; ``完全マッチングを持つグラフに対する最小頂点被覆問題の近似解法'',; 夏のLAシンポジウム, pp.5.1--5.9, 2002年 7月.

id=2002-16: 上嶋章宏, 伊藤大雄,; ``平面グラフの$\overline{C_7}$-彩色問題'',; 夏のLAシンポジウム, 2002年 7月.; >> Abstract

id=2002-17: 土井伸洋, 堀山貴史, 中西正樹, 木村晋二, 渡邉勝正,; ``浮動小数点を含むCプログラムからのハードウェア生成におけるビット長最適化'',; 情報処理学会 DAシンポジウム2002, pp.119--124, 2002年 7月.

id=2002-18: 梶原裕嗣, 堀山貴史, 中西正樹, 木村晋二, 渡邉勝正,; ``論理関数の畳み込みを考慮したLook Up Tableの設計と実現'',; 情報処理学会 DAシンポジウム2002, pp.223--228, 2002年 7月.

id=2002-22: 松浦昭洋, 岩間一雄,; ``$k$-CNF式に対するInclusion-Exclusion公式について'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.102, no.258, COMP2002-28, pp.45--51, 2002年 8月.; >> Abstract

id=2002-26: 渡邉勝正, 小林郁典, 中西正樹, 堀山貴史, 木村晋二,; ``アクティブソフトウェアの動的変更について'',; 日本ソフトウェア科学会第19回大会, 4F-1, 2002年 9月.

id=2002-27: 河内亮周, 岩間一雄,; ``3関数に対する量子クロー探索アルゴリズム'',; 情報科学技術フォーラム; FIT, vol.1, pp.1--2, 2002年 9月.; >> Abstract

id=2002-28: 田村武幸, 土田大輔, 伊藤大雄, 岩間一雄,; ``DNA配列におけるプローブの順序付けに必要な最小フラグメント集合'',; 情報技術レターズ (情報科学技術フォーラム; FIT), vol.1, pp.5--6, 2002年 9月.; >> Abstract

id=2002-29: 柳澤弘揮, 宮崎修一, 岩間一雄, マグナスハルダースソン,; ``ランダムタイブレークによる安定マッチングの導出'',; 情報技術レターズ (情報科学技術フォーラム; FIT), vol.1, pp.13--14, 2002年 9月.; >> Abstract

id=2002-30: 松浦昭洋,; ``$k$-CNF式に対するInclusion-Exclusion公式における非充足解数計算手法'',; 情報技術レターズ (情報科学技術フォーラム; FIT), vol.1, A-25, pp.49--50, 2002年 9月.; >> Abstract

id=2002-31: 今村友和, 岩間一雄,; ``完全マッチングを持つグラフに対する最小頂点被覆問題の近似解法'',; 情報技術レターズ (情報科学技術フォーラム; FIT), vol.1, pp.23--24, 2002年 9月.

id=2002-32: 上嶋章宏, 伊藤大雄,; ``平面グラフの$\overline{C_7}$-彩色問題'',; 情報処理学会アルゴリズム研究会, 情処研報, 2002-AL-86, pp.67--74, 2002年 9月.; >> Abstract

id=2002-44: K. Iwama, A. Kawachi, H. Masuda, Rudy Raymond H.P., and S. Yamashita,; ``Quantum query complexity and the number of inverted states'',; 電子情報通信学会第7回量子情報技術研究会, Nov. 2002.; >> Abstract

id=2002-45: 渡邉勝正, 相良かおる, 山下隆義, 中西正樹, 堀山貴史, 木村晋二,; ``ことばによる手話単語の記述と三次元表現'',; 日本機械学会第2回福祉工学シンポジウム, 8C45, pp.189--192, 2002年 11月.

id=2002-46: 土井伸洋, 堀山貴史, 中西正樹, 木村晋二, 渡邉勝正,; ``Cプログラムからの合成における浮動小数点演算のビット長最適化'',; 第6回システムLSIワークショップ, pp.263--266, 2002年 11月.

id=2002-47: 吉廣卓哉, 伊藤大雄, 岡部寿男, 岩間一雄,; ``最短路ルーティングにおけるバックアップテーブルに関する考察'',; 電子情報通信学会コンピュテーション研究会, 信学技報, COMP2002-53, pp.1--7, 2002年 12月.; >> Abstract

id=2002-50: 柳澤弘揮, 宮崎修一, 岩間一雄, M. Halld\'orsson,; ``長さ2のタイを含む安定結婚問題に対する近似アルゴリズム'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.102, no.522, COMP2002-59, pp.41--47, 2002年 12月.; >> Abstract

id=2002-53: 梶原裕嗣, 中西正樹, 堀山貴史, 木村晋二,; ``論理関数の畳み込み機構を導入した省面積 FPGA の実現と評価'',; 電子情報通信学会設計技術研究会, 信学技報, VLD2002-126, CPSY2002-79, pp.37--42, 2003年 1月.

id=2002-54: 江原康生, 高倉弘喜, 宮崎修一, 中村素典, 沢田篤史, 岡部寿男, 金澤正憲,; ``安全なギガビットネットワーク KUINS-IIIの構築と運用'',; 分散システム／インターネット運用技術シンポジウム2003, pp.19--24, 2003年 1月.

id=2002-55: 増田裕之, Rudy Raymond H.P., 河内亮周, 山下茂, 岩間一雄,; ``探索問題における一般的な量子オラクルの質問回数について'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.102, COMP2002-70, 2003年 1月.; >> Abstract

id=2002-58: 佐久間俊慎, 小野廣隆, 山下雅史, 朝廣雄一, 牧野和久, 堀山貴史,; ``ボール回収問題におけるロボットスケジューリング問題'',; 冬のLAシンポジウム, 数理解析研究所講究録 1325, pp.8--14, 2003年 2月.

id=2002-60: 田村武幸, 伊藤大雄, 岩間一雄,; ``DNA配列のプローブ順序固定に必要な最小フラグメント集合'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.102, no.733, COMP2002-77, 2003年 3月.; >> Abstract

[ 解説 ]

id=2002-20: 岩間一雄, 山下茂,; ``量子コンピュータ科学入門'',; 電子情報通信学会誌, vol.85, no.8, pp.618--625, 2002年 8月.; >> Abstract

[ その他 ]

id=2002-38: M. Halld\'orsson, R Irving, K. Iwama, D. Manlove, S. Miyazaki, Y. Morita, and S. Scott,; ``Approximability Results for Stable Marriage Problems with Ties'',; Technical Report of the Computing Science Department, TR-2002-121, Glasgow University, Oct. 2002.

Abstract

id=2002-01: The stable marriage problem has received considerable attention both due to its practical applications as well as its mathematical structure. While the original problem has all participants rank all members of the opposite sex in a strict order of preference, two natural variations are to allow for incomplete preference lists and ties in the preferences. Both variations are polynomially solvable by a variation of the classical algorithm of Gale and Shapley. On the other hand, it has recently been shown to be NP-hard to find a maximum cardinality stable matching when both of the variations are allowed. We show here that it is APX-hard to approximate the maximum cardinality stable matching with incomplete lists and ties. This holds for some very restricted instances both in terms of lengths of preference lists, and lengths and occurrences of ties in the lists. We also obtain an optimal $\Omega(N)$ hardness results for 'minimum egalitarian' and 'minimum regret' variants.

id=2002-04: Coloring problem is a well-known combinatorial optimization problem of graphs. This paper considers {\it $H$-coloring problems}, which are coloring problems with restrictions such that some pairs of colors can not be used for adjacent vertices. The restriction of adjacent colors can be represented by a graph $H$, i.e., each vertex represents a color and each edge means that the two colors corresponding to the two end-vertices can be used for adjacent vertices. Especially, $H$-coloring problem with a complete graph $H$ of order $k$ is equivalent to the traditional $k$-coloring problem. This paper presents sufficient conditions such that $H$-coloring problem can be reduced to an $H'$-coloring problem, where $H'$ is a subgraph of $H$. And it shows a hierarchy about classes of $H$-colorable graphs for any complement graph $H$ of a cycle of order odd $n \geq 5$.

id=2002-05: We show that the number of satisfying assignments of a $k$-CNF formula is determined uniquely from the numbers of unsatisfying assignments for clause-sets of size up to $\lfloor \log k \rfloor + 2$. This amount of information is also shown to be necessary.

id=2002-06: The Goldreich Levin(GL) problem asks to find $a$ from a noisy Inner Product (IP) oracle with bias $\epsilon$ and an exact Equality (EQ) oracle which are correlated with $a$. An interesting question arises on whether we can solve the GL problem without EQ queries. However, it has been known that using IP queries alone, the GL problem cannot be solved in the sense that the solution $a$ is not unique. Here, we investigate the noisy IP problem, that is, given a noisy IP oracle our task is to find all $a$ which are correlated with the noisy IP oracle within bias $\epsilon$. We show a lower bound of queries for such algorithm. This also implies a lower bound for any algorithm which uses EQ oracle in quantum amplitude amplification scheme.

id=2002-07: 近年，現実的なネットワークモデルを用いて伸張係数３で各頂点のルーティングテーブルサイズを$O(n^{2/3} \log^{4/3} n)$に抑えるコンパクトルーティングアルゴリズムが提案されている．この伸張係数３は一般的な下限と一致し，同じモデルを用いて伸張係数３未満に制限するとテーブルサイズの上下限が$(1 - o(1)) n \log n$まで増加してしまう具合の悪いネットワークが存在する．それに対して，本稿では平均的なグラフが持つ望ましい条件として平坦性という概念を導入し，グラフが$(\alpha, s, \gamma, \delta)$-疑似平坦である時，伸張係数$s \kern1ex(s < 3)$でテーブルサイズ$O\left( \left( n^{1 - \alpha} \log n + \gamma n^\alpha \right) \log n\right)$のコンパクトルーティングアルゴリズムを示す．特に$\gamma$ を定数に定めることができるとき，テーブルサイズは$O(\sqrt{n \log n})$まで削減することができる．

id=2002-08: IPv6のサイトローカルアドレスをゼロ設定（zeroconf）でステートレスに自動割り当てする枠組を提案する．当該リンクに最初に接続されたルータが，そのリンクのリーダとなって，16bitのsubnet ID部分をランダムに選んだプレフィックスを生成する．アドレスのサイト内での一意性を保証するために， RIPng を拡張したプレフィックスアドレス重複の検出方法を示す．重複が検出されると直ちにリンクリーダへ通知され，IPv6のアドレス付替の仕組を用いて新たなアドレスへの付替が行われる．また，新旧のアドレスが共存できるIPv6の特徴を生かし，古いアドレスを用いた既存通信を一定時間保護する経路制御を実現した．

id=2002-09: Suppose that some particular link in the Internet is currently congested. Then a natural idea is to try to make packets bypass that link. This can be done by increasing the cost of that link intentionally, say from $a_1$ to $a_2$, since the Internet uses the shortest-path routing. Unfortunately, however, this often causes temporary loops for packet traveling, called {\it routing loops}. In this paper, we show that routing loops can be avoided by increasing the cost of the link not directly from $a_1$ to $a_2$ but through an intermediate value, $a_3$, i.e., from $a_1$ to $a_3$ and then to $a_2$. We may need several (more than one) intermediate values. We show that in such a occasion, the greedy strategy, namely raising the cost as much as possible in each step, is optimal.

id=2002-10: This paper gives a simple but nontrivial set of local transformation rules for {\it Control-NOT}({\it CNOT})-based combinatorial circuits. It is shown that this rule set is complete, namely, for any two equivalent circuits, $S_1$ and $S_2$, there is a sequence of transformations, each of them in the rule set, which changes $S_1$ to $S_2$. Our motivation is to use this rule set for developing a design theory for {\it quantum circuits} whose Boolean logic parts should be implemented by CNOT-based circuits.

id=2002-11: あるリンクで輻輳が発生した場合，それを迂回するようにパケットの経路を変更することは，自然な解決方法の一つである．これを実現するのは容易である．輻輳したリンクのコストを，例えば $a_1$ から $a_2$ へというように上げさえすれば良い．しかし，この方法では，しばしば一時的な通信経路のループが生じ，一度パケットが巻き込まれてしまうと，宛先に到達することができなくなる．本稿では，コストを直接 $a_1$ から $a_2$ に上げるのではなく， $a_3$ を経由することで(つまり，一度 $a_1$ から $a_3$ に上げてから，改めて $a_3$ から$a_2$ に上げることで)，このようなループを避ける手法を提案する．また，コストを望ましい値まで上げるためにはいくつかの中間値を経なければならない場合がある．このとき，より少ないステップ数でその値まで上げるには，各ステップでループが生じない最大値まで上げる，いわば欲張りな戦略が最適であることを示す．

id=2002-12: We introduce an on-line model for a class of hand-making games such as Rummy and Mah-Jang. An input is a sequence of items, $u_{1}, \cdots, u_{i}, \cdots$ such that $0 < \vert u_{i}\vert \leq 1.0$. When $u_i$ is given, the on-line player puts it into the bin and can discard any selected items currently in the bin (including $u_i$) under the condition that the total size of the remaining items is at most one. The goal is to make this total size as close to 1.0 as possible when the game ends. We also discuss the multi-bin model, where the player can select a bin out of the $k$ ones which $u_i$ is put into. We prove tight bounds for the competitive ratio of this problem, both for $k=1$ and $k \geq 2$.

id=2002-13: Compact routing has a long history of research, whose goal is to reduce the size of a routing table being stored in each processor. The size of the routing table usually has a trade-off against the stretch factor, i.e., the ratio of the length of the path computed by the algorithm over the length of the shortest path. Cowen presented a universal compact routing algorithm with a stretch factor of three and a table-size of $O(n^{2/3} \log^{4/3} n)$, based on a simple and practical model. This stretch factor of three matches a general lower bound and also matches a much tighter lower bound if we restrict the model. Thus it seems hard to improve the Cowen's result. It should be noted, however, that her analysis is of course for the worst case. Our scenario can be different if we assume some desirable property that average-case networks often have. For such a property, we introduce the notion of flatness in this paper. Roughly speaking, a network is said to be flat if the distribution of the distances between nodes is not extreme. It is shown that both the stretch factor and the size of the routing table can be significantly improved if the given network is almost flat, i.e., is flat if a certain set of nodes are removed. We can enjoy this improved performance without changing the (simple and nice) structure of the Cowen's algorithm.

id=2002-16: 本稿では，グラフの点彩色問題を一般化した問題である，$H$-彩色問題について研究を扱う(但し，$H$はグラフである)．本問題は，従来の点彩色問題に，``隣接点対に塗れないような異なる色対も存在し得る''という単純な一般化を加えた問題と言え，移動体通信システムにおいて基地局への使用周波数帯域の割当てに関連した問題などに応用できる．本稿では特に，平面グラフの $\overline{C_7}$-彩色問題を研究対象とし，これまでに得られた様々な性質を示す(但し，$\overline{C_7}$は長さ7の閉路の補グラフである)．

id=2002-19: The current best lower bound of $4.5n-o(n)$ for an explicit family of Boolean circuits is improved to $5n-o(n)$ using the same family of Boolean function.

id=2002-20: 本稿では，現在注目を集めている量子コンピュータについて計算機科学的な視野で，アルゴリズムを設計する際に必要となる基本事項についてまとめる．まず，量子計算のモデルとして量子チューリング機械および量子回路について概説する．次に，量子アルゴリズムとしてGroverの探索アルゴリズムを取り上げ，種々のアルゴリズム的な観点から，その応用の仕方や拡張方法について議論をする．最後に量子コンピュータの計算能力について，計算量クラスの立場からの研究について知られている主な結果をまとめる．

id=2002-22: $k$-CNF論理式の非充足解の総数をInclusion-Exclusion公式を用いて求める方法が知られている。$m$項から成る$k$-CNF式において、公式中全ての項の組合せ（$2^m$通り）に対して、各項集合に含まれる全ての項を非充足にする変数割当ての数を求める必要がある。本稿では、Inclusion-Exclusion公式に基づいた非充足解総数の計算において、$m$項のうち高々 $\lfloor \log k \rfloor + 2$個の項集合全体に関して非充足解の情報を持つことが、元の$k$-CNF式の非充足解総数を一意に定めるための必要十分条件であることを示す。

id=2002-23: Let $G=(V,E)$ be an undirected multigraph where $V$ and $E$ are a set of vertices and a set of edges, respectively. Let $k$ and $l$ be fixed nonnegative integers. This paper considers location problems of finding a minimum size vertex-subset $S \subseteq V$ such that for each vertex $x \in V$ the vertex-connectivity between $S$ and $x$ is greater than or equal to $k$ and the edge-connectivity between $S$ and $x$ is greater than or equal to $l$. For the problem with edge-connectivity requirements, i.e., $k = 0$, an $O(L( |V|, |E|, l))$ time algorithm is already known, where $L(|V|, |E|, l)$ is the time to find all $h$-edge-connected components for $h = 1,2, \ldots, l$ and $O(L( |V|, |E|, l))$ $= O(|E| + |V|^2 + |V| \mbox{min}\{ |E|, l |V| \} \mbox{min}\{ l, |V| \})$ is known. In this paper we show that the problem with $k \geq 3$ is NP-hard even for $l=0$. We then present an $O(L(|V|, |E|, l))$ time algorithm for $0 \leq k \leq 2$ and $l \geq 0$. Moreover, we prove that the problem parameterized by the size of $S$ is FPT (fixed parameter tractable) for $k=3$ and $l \geq 0$.

id=2002-24: The Goldreich Levin (GL) problem asks to find $a$ from a noisy Inner Product (IP) oracle with bias $\epsilon$ and an exact Equality (EQ) oracle which are correlated with $a$. An interesting question arises on whether we can solve the GL problem without EQ queries. However, it has been known that using IP queries alone, the GL problem cannot be solved in the sense that the solution $a$ is not unique. Here, we investigate the noisy IP problem, that is, given a noisy IP oracle our task is to find all $a$ which are correlated with the noisy IP oracle within bias $\epsilon$. We define {\it strong solvability} for List Decoding Problem of parity coding and prove its lower bound. This also implies the lower bound of any algorithm which uses {\it strong solvability} to solve the GL problem.

id=2002-25: In this paper, we show that Ambainis's lower bound technique can be utilized to show that the quantum query complexity for determining a solution among $N$ possible inputs is $\Omega(\sqrt{N/K})$ under a proper assumption, where $K$ is the number of quantum states inverted by one quantum oracle call. We also show that there exists a quantum oracle by which we can determine a solution with $O(\sqrt{N/K})$ queries. Our result can be seen as generalization which covers the query complexities of both IP and EQ oracles, and supports our conjecture that the above number, $K$, relates to the quantum query complexity.

id=2002-27: $k$個の関数$f_1,...,f_k$に対して$f_1(x_1)=\cdots =f_k(x_k)$を満たす入力の組$(x_1,...,x_k)$を$f_1,...,f_k$のクローと呼ぶ．本稿では3関数$f, g, h$のクロー探索に対して，$f,g$のクロー（中間解）にある制約を加えたときに高速化されることを論じる． \cite{B+01}では$k$個の関数の場合には関数$f_1,...,f_k$の計算回数が$O(n^{1-1/2^k}\log n)$，特に$k=3$の場合は $O(n^{7/8}\log n)$であるが，我々のアルゴリズムは$m\leq \sqrt{n}$のときは$O(n^{3/4}\log n)$，$m>\sqrt{n}$のときは$O(n^{7/12}m^{1/3}\log n)$の計算回数により定数確率で3関数のクローを求めることができる．ここで$m$は中間解の個数である．つまり$m\leq n^{7/8}$のときには我々のアルゴリズムの方が高速である．

id=2002-28: ゲノム解析の手法のひとつとして、塩基の文字列(プローブ)が DNAの部分配列(フラグメント)に含まれるかどうか調べる方法がある。本稿ではプローブの順序を一意に決定する問題を扱う。プローブの順序を一意に決定するためにはフラグメントを追加する必要がある。本稿ではプローブの順序を一意に決定するために必要な最小フラグメント数を求める線形時間アルゴリズムについて示す。

id=2002-29: 安定結婚問題とは、提出された希望リストに基づき、ある安定条件を満たすマッチングを求める問題である。従来の安定結婚問題では、希望リストに異性全員を全順序で記述する必要があった。タイ(同順位)を含んだ希望リストや不完全な希望リストを許すと、最大サイズの安定マッチングを求める問題はNP 困難になる。この問題に対する2-近似アルゴリズムは容易に作ることができるが、近似度が2よりも小さいアルゴリズムは知られていない。本研究では、タイを男性のみに認め、各男性が持てるタイを一つに制限し、タイの長さを2に制限した、比較的自然な例題集合に対して、近似度が10/7の確率近似アルゴリズムと近似度が20/11の決定性近似アルゴリズムを与えた。

id=2002-30: $k$-CNF式の非充足解の総数を求める際、Inclusion-Exclusion公式を用いるのは標準的な方法である。公式中、全ての項の組合せ、すなわち項数を$m$としたとき、$2^m$個の項集合に対して、それらの項集合を非充足にする変数割り当ての数を評価する必要があるが、最近、$\lfloor \log k \rfloor + 2$ 個までの項の非充足解の情報が分かれば、元の式の非充足解の数は既に一意に定まっているという事実が示された。しかしそこでは、非充足解の数がある数に一意に決まっていることが``存在定理''として示されたものの、 $\lfloor \log k \rfloor + 2$個までの項に関する非充足解の数の情報から、それ以上の項数に関する非充足解の数を実際に計算する手法については分かっていなかった。本稿では、一般のCNF式に関する結果を拡張することにより、そのようなアルゴリズムが存在することを示す。

id=2002-32: 本稿では，グラフの点彩色問題の一般化である，$H$-彩色問題を扱う(但し， $H$はグラフ)．特に$H$が奇数長閉路の補グラフ$\overline{C_p}$($p$は節点数)である場合を取り上げ，以下の性質を示す：(1) $m$-彩色可能であるとき，かつそのときに限り，$\overline{C_{2m+1}}$-彩色可能であるような、グラフのクラスの提示，(2) 平面グラフの$\overline{C_7}$-彩色問題の NP-完全性の証明，(3) $\overline{C_7}$-彩色可能であるが，3-彩色不可能な平面グラフのクラスの提示．

id=2002-33: A location problem in a network is to determine the best location of facilities in a given network that satisfies certain constraints, where an objective function and constraints are specified according to the problem to be considered. Recently, location problems involving vertex-connectivity or edge-connectivity have been treated and several polynomial-time algorithms have been developed. So-called {\em source location problems} are to find the minimum-cost location of sources under connectivity requirements in networks. Source location problems have some variations, for example, graphs are undirected graphs or digraphs, the connectivity is based on vertex-connectivity or edge-connectivity, etc. This paper surveys them and shows some resent results.

id=2002-35: 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 ran 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=2002-36: The main purpose of this paper is to show that we can exploit the difference ($l_1$-norm and $l_2$-norm) in the probability calculation between quantum and probabilistic computations to claim the difference in their space efficiencies. It is shown that there is a finite language $L$ which contains sentences of length up to $O(n^{c+1})$ such that: ($i$) There is a one-way quantum finite automaton (qfa) of $O(n^{c+4})$ states which recognizes $L$. ($ii$) However, if we try to simulate this qfa by a probabilistic finite automaton (pfa) \textit{using the same algorithm}, then it needs $\Omega(n^{2c+4})$ states. It should be noted that we do not prove real lower bounds for pfa's but show that if pfa's and qfa's use exactly the same algorithm, then qfa's need much less states.

id=2002-37: This paper gives a simple but nontrivial set of local transformation rules for CNOT-based quantum circuits. It is shown that this rule set is complete, namely for any two equivalent circuits, $S_1$ and $S_2$, there is a sequence of transformations, each of them in the rule set, which changes $S_1$ to $S_2$. This rule set can be used for incremental circuit optimization methods like the classical circuit design methodology.

id=2002-39: We study the online version of the independent set problem in graphs. The vertices of an input graph are given one by one along with their edges to previous vertices, and the task is to decide whether to add each given vertex to an independent set solution. The goal is to maximize the size of the independent set, relative to the size of the optimal independent set. Since it is known that no online algorithm can attain competitive ratio better than $n-1$, where $n$ denotes the number of vertices, we study here relaxations where the algorithm can hedge its bets by maintaining multiple alternative solutions. We introduce two models. In the first model, the algorithm can maintain a multiple number ($r(n)$) of solutions (independent sets) and choose the largest one as the final solution. We show that the best competitive ratio for this model is $\theta(\frac{n}{\log n})$ when $r(n)$ is a polynomial and $\theta(n)$ when $r(n)$ is a constant. In the second more powerful model, the algorithm can copy intermediate solutions and extend the copied solutions in different ways. We obtain an upper bound $O(n/ \log n)$ and a lower bound $\Omega(n/\log^3 n)$ for the best possible competitive ratio when $r(n)$ is a polynomial. Furthermore, we show a tight $\theta(n)$ bound when $r(n)$ is a constant. Lower bound results of this paper hold also for randomized online algorithms against an oblivious adversary.

id=2002-40: We propose a new framework for stateless autoconfiguration of IPv6 site-local addresses with ``zero configuration.'' When a router is connected to a link as the first router, it becomes the link leader and generates an address prefix with randomly generated 16-bit subnet ID for the link. In order to assure the uniqueness of the prefix addresses, we show a protocol, which is an extension of RIPng, for detecting prefixes conflicts. When a conflict is detected, its link leader is notified of it immediately. The link leader generates a new prefix and renumber to new one via IPv6 address renumbering scheme.

id=2002-41: Given an edge-weighted digraph $G$ with a designated vertex $r$, and a vertex capacity $\delta$, we consider the problem of finding a shortest path tree $T$ rooted at $r$ such that for each vertex $v$ the number of children of $v$ in $T$ does not exceed the capacity $\delta(v)$. The problem has an application in designing a routing for transferring files from the source node to other nodes in an information network. In this paper, we first present an efficient algorithm to the problem. We then introduce extensions of the problem by relaxing the degree constraint or the distance constraint in various ways and show polynomial algorithms or the computational hardness of these problems.

id=2002-42: Let $s$ be the ratio of the cost for purchasing skis over the cost for renting them. Then the famous result for the ski-rental problem shows that skiers should buy their skis after renting them $(s-1)$ times, which gives us an optimal competitive ratio of $2-\frac{1}{s}$. In practice, however, it appears that many skiers buy their skis before this optimal point of time and also many skiers keep renting them forever. In this paper we show that these behaviors of skiers are quite reasonable by using an {\em average-case competitive ratio}. For an exponential input distribution $f(t) = \lambda e^{-\lambda t}$, optimal strategies are (i) if $\frac{1}{\lambda} \leq s$, then skiers should rent their skis forever and (ii) otherwise should purchase them after renting approximately $s^2\lambda \;\;(<s)$ times. Thus average-case competitive analyses give us the result which differs from the worst-case competitive analysis and also differs from the traditional average cost analysis. Other distributions and related problems are also discussed.

id=2002-44: In this paper, we show that Ambainis's lower bound technique can be utilized to show that the quantum query complexity for determining a solution among $N$ possible inputs is $\Omega(\sqrt{N/K})$ under a proper assumption, where $K$ is the number of quantum states inverted by one quantum oracle call. We also show that there exists a quantum oracle by which we can determine a solution with $O(\sqrt{N/K})$ queries. Our result can be seen as generalization which covers the query complexities of both {\it inner product (IP)} and {\it equivalence (EQ)} oracles, and supports our conjecture that the above number, $K$, relates to the quantum query complexity.

id=2002-47: 最短路木に基づいた経路制御がされているネットワークにおいて，第2のルーティングテーブル（バックアップテーブル）を計算しておき，枝（リンク）故障を発見したノードが瞬時にテーブルを切り替えることで，途切れることなく通信を継続できる方式を提案する．我々の方式を用いると， 2枝連結な有向対称グラフで表されるどのようなネットワークに対しても，任意の一本の枝故障を回復できるようなバックアップテーブルが存在することが保証される．また，最適なバックアップテーブルを計算する最適化問題を定義し，各枝の長さが均一な場合にこれを線形時間で解くアルゴリズムを構成する．

id=2002-49: Given a hypergraph $H$ with a vertex set $N = \{ 0, 1, \ldots, n-1 \}$ and an $n$-gon $P$ in the plane, we define the area $A_P(H)$ of $H$ on $P$ by the sum of areas of hyperedges in $H$ when each $i\in N$ is drawn on a vertex in $P$. We give some conditions for two hypergraphs $H$ and $H'$ on $N$ to satisfy $A_P(H)\leq A_P(H')$ for all $n$-gons $P$.

id=2002-50: 安定結婚問題とは，提出された希望リストに基づき，ある安定条件を満たすマッチングを求める問題である．従来の安定結婚問題では，希望リストに異性全員を全順序で記述する必要があった．タイ（同順位）を含んだ希望リストや不完全な希望リストを許すと，最大サイズの安定マッチングを求める問題は NP 困難になる．この問題に対する2-近似アルゴリズムは容易に作ることができるが，近似度が2よりも小さいアルゴリズムは知られていない．本研究では，タイの長さを2に制限した比較的自然な例題集合に対して，近似度が$25/13 (< 1.924)$ の近似アルゴリズムを与えた．

id=2002-51: Let $x_0, x_1, ..., x_{n-1}$ be vertices of a convex $n$-gon $P$ in the plane, where, $x_0 x_1$, $x_1 x_2$, $\ldots$, $x_{n-2} x_{n-1}$, and $x_{n-1} x_0$ are edges of $P$. Let $G = (N, E)$ be a multigraph, such that $N = \{ 0, 1, \ldots, n-1 \}$. Consider a graph-drawing of $G$ such that each vertex $i \in N$ corresponds $x_i$ and each edge $(i,j) \in E$ is drawn by a straight line segment. Denote the sum of the lengths of the edges of $G$ in such a drawing by $S_P(G)$. If $S_P(G) \leq S_P(G')$ for any convex $n$-gon $P$, then we write as $G \preceq_l G'$. This paper shows two necessary and sufficient conditions of $G \preceq_l G'$. Moreover, these conditions can be calculated in polynomial time for any given $G$ and $G'$.

id=2002-52: Let $H$ be a hypergraph with a node set $N=\{0, 1, \ldots, n-1\}$. Given an $n$-gon $P$ with a vertex set $\{ x_0, x_1, \ldots, x_{n-1} \}$ in the plane, we define a projection of $H$ on $P$ by mapping each node $i\in N$ to the vertex $x_i$ and drawing each hyperedge $e$ in $H$ by the convex hull of the vertices $x_j$ such that $j$ is an end node of $e$, where we say that $e$ covers every point $p$ in the interior of the convex hull. We say that $H$ {\em covers} $P$ if any point in the interior of $P$ is covered by at least one hyperedge of $H$. In this paper, we consider the problem of determining whether or not a given hypergraph $H$ with an ordered node set covers {\em every} convex polygon and give a polynomial time algorithm to the problem. We also consider the problem of computing the smallest thickness of a point $p$ (i.e., the smallest number of hyperedges that cover $p$) in a projection of $H$ on all $n$-gons $P$, and solve the problem by a reduction to the maximum flow problem.

id=2002-55: 量子探索問題はアルゴリズムが解についての情報を得ることのできるオラクルにより特徴づけられる．そのオラクルは$f(a,x): \{0,1\}^n\times\{0,1\}^n \rightarrow \{0,1\}$ で定義され，例えば$EQ$オラクルは$f(a,x)=1$ iff $x=a$で定義される． $N = 2^n$とし，$N\times N$の真理値表$T_f$のオラクル$f$が与えられたとする．また$K$を$T_f$の一列における$1$の個数の最大値とする．本研究ではその際，探索問題のクエリー回数がこのパラメータ$K$に大きく依存すること，つまり以下の三つのことを示す． ($i$) クエリー回数は$\Omega(\sqrt{N/K})$である． ($ii$) クエリー回数が$O(\sqrt{N/K})$であるオラクルが存在する． ($iii$) 古典で計算した場合のクエリー回数の下界が$\Omega(N/K+\log{K})$で$O(N/K+\log{K})$ であるオラクルも存在する．

id=2002-56: In this paper, we consider two types of {\it promises} for ($k$-)CNF formulas which can help to find a satisfying assignment of a given formula. The first promise is the Hamming distance between truth assignments. Namely, we know in advance that a $k$-CNF formula with $n$ variables, if satisfiable, has a satisfying assignment with at most $pn$ variables set to 1. Then we ask whether or not the formula is satisfiable. It is shown that for $k \ge 3$ and (i) when $p=n^c$ ($-1 < c \le 0$), the problem is NP-hard; and (ii) when $p=\log n / n$, there exists a polynomial-time deterministic algorithm. The algorithm is based on the exponential-time algorithm recently presented by U. Sch\"{o}ning. It is also applied for coloring $k$-uniform hypergraphs. The other promise is the number of satisfying assignments. For a CNF formula having $2^n/2^{n^{\epsilon}}$ $(0 \le \epsilon < 1)$ satisfying assignments, we present a subexponential-time deterministic algorithm based on the inclusion-exclusion formula.

id=2002-60: ゲノム解析の手法のひとつとして、塩基の文字列(プローブ)が DNAの部分配列(フラグメント)に含まれるかどうか調べる方法がある。どのプローブがどのフラグメントに存在するかによって、プローブやフラグメントの順序が決定されていく。また、多くのフラグメントを調べるほど、プローブの順序が正確に判明していく。本稿ではプローブの順序を固定するために、どのような追加フラグメント集合が必要かについて議論する。プローブとフラグメントの関係は、フラグメントの存在するところを1、存在しないところを0として、プローブを列、フラグメントを行に対応させることにより、(0,1)-行列によって表現することができる。本稿で扱う問題は、与えられた(0,1)-行列に、新たに行を追加して、各行の1が連続するような列の順序を一意に固定する問題である。 (0,1)-行列における1を連続させうる列の順序集合を表現するには、 PQ木というデータ構造を用いると便利である。本稿ではこのPQ木に対し、種々の条件のもとで、プローブの順序を一意に固定するのに必要な追加フラグメント集合の性質を解析し、最小フラグメント集合を求める多項式時間アルゴリズムを示した。

岩間研究室 発表論文

2002年度

[ 論文誌 ]

[ 国際会議 ]

[ 国内発表 ]

[ 解説 ]

[ その他 ]

Abstract

岩間研究室発表論文