# 岩間研究室 発表論文

## [ 論文誌 ]

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$の下限'',

id=2002-06
K. Iwama, Rudy Raymond H.P., S. Yamashita, and T. Yamakami,
Quantum complexity of noisy IP query'',

>> Abstract
id=2002-07

平坦なグラフに対するコンパクトルーティング'',

>> Abstract
id=2002-11

インターネットにおける経路ループの回避手法'',

>> Abstract
id=2002-14

直線軌道移動するロボットによるボール回収問題'',

id=2002-15

完全マッチングを持つグラフに対する最小頂点被覆問題の近似解法'',

id=2002-16

平面グラフの$\overline{C_7}$-彩色問題'',

>> Abstract
id=2002-17

浮動小数点を含むCプログラムからのハードウェア生成におけるビット長最適化'',

id=2002-18

論理関数の畳み込みを考慮したLook Up Tableの設計と実現'',

id=2002-22

$k$-CNF式に対するInclusion-Exclusion公式について'',

>> Abstract
id=2002-26

アクティブソフトウェアの動的変更について'',

id=2002-27

3関数に対する量子クロー探索アルゴリズム'',

>> Abstract
id=2002-28

DNA配列におけるプローブの順序付けに必要な最小フラグメント集合'',

>> Abstract
id=2002-29

ランダムタイブレークによる安定マッチングの導出'',

>> Abstract
id=2002-30

$k$-CNF式に対するInclusion-Exclusion公式における非充足解数計算手法'',

>> Abstract
id=2002-31

完全マッチングを持つグラフに対する最小頂点被覆問題の近似解法'',

id=2002-32

平面グラフの$\overline{C_7}$-彩色問題'',

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

>> Abstract
id=2002-45

ことばによる手話単語の記述と三次元表現'',

id=2002-46

Cプログラムからの合成における浮動小数点演算のビット長最適化'',

id=2002-47

最短路ルーティングにおけるバックアップテーブルに関する考察'',

>> Abstract
id=2002-50

長さ2のタイを含む安定結婚問題に対する近似アルゴリズム'',

>> Abstract
id=2002-53

論理関数の畳み込み機構を導入した省面積 FPGA の実現と評価'',

id=2002-54

安全なギガビットネットワーク KUINS-IIIの構築と運用'',

id=2002-55

探索問題における一般的な量子オラクルの質問回数について'',

>> Abstract
id=2002-58

ボール回収問題におけるロボットスケジューリング問題'',

id=2002-60

DNA配列のプローブ順序固定に必要な最小フラグメント集合'',

>> Abstract

## [ 解説 ]

id=2002-20

量子コンピュータ科学入門'',

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

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

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

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

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

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

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

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

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木に対し、種々の条件のもとで、プローブの順序を 一意に固定するのに必要な追加フラグメント集合の性質を解析し、 最小フラグメント集合を求める多項式時間アルゴリズムを示した。