岩間研究室発表論文

2004年度

[ 論文誌 ]

id=2004-02: A. Uejima, H. Ito, and T. Tsukiji,; ``$\overline{C_7}$-coloring problem'',; IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol.E87-A, no.5, pp.1243--1250, May 2004.; >> Abstract

id=2004-04: K. Iwama, and K. Yonezawa,; ``The Orthogonal CNN Problem'',; Information Processing Letters, vol.90, no.3, pp.115--120, May 2004.; >> Abstract

id=2004-05: K. Iwama, and K. Yonezawa,; ``The Axis-bound CNN Problem'',; IEICE Transactions on Fundamentals, vol.87E-A, no.5, pp.1235--1242, May 2004.; >> Abstract

id=2004-14: T. Horiyama, and T. Ibaraki,; ``Reasoning with Ordered Binary Decision Diagrams'',; Discrete Applied Mathematics, vol.142/1-3, pp.151--163, Aug. 2004.; >> Abstract

id=2004-19: M. Halld\'orsson, K. Iwama, S. Miyazaki, and H. Yanagisawa,; ``Randomized Approximation of the Stable Marriage Problem'',; Theoretical Computer Science, vol.325, no.3, pp.439--465, Oct. 2004.; >> Abstract

id=2004-23: H. Miwa, and H. Ito,; ``NA-Edge-Connectivity Augmentation Problems by Adding Edges'',; Journal of the Operations Reserch Society of Japan, vol.47, no.4, pp.224--243, Dec. 2004.; >> Abstract

id=2004-24: K. Iwama, A. Kawachi, and S. Yamashita,; ``Quantum Sampling for Balanced Allocations'',; IEICE Trans. Inf. \& Syst., Special Issue on Foundations of Computer Science, vol.E88-D, no.1, pp.39--46, Jan. 2005.; >> Abstract

id=2004-25: K. Iwama, and A. Kawachi,; ``Compact Routing with Stretch Factor of Less Than Three'',; IEICE Trans. Inf. \& Syst., Special Issue on Foundations of Computer Science, vol.E88-D, no.1, pp.47--52, Jan. 2005.; >> Abstract

id=2004-31: H. Fujiwara, and K. Iwama,; ``Average-Case Competitive Analyses for Ski-Rental Problems'',; Algorithmica, vol.42, no.1, pp.95--107, Mar. 2005.; >> Abstract

id=2004-34: H. Ito, K. Iwama, Y. Okabe, and T. Yoshihiro,; ``Single-Backup-Table Schemes for Shortest-Path Routing'',; Theoretical Computer Science, vol.333, no.3, pp.347--353, Mar. 2005.; >> Abstract

[ 国際会議 ]

id=2004-03: A. Uejima, and H. Ito,; ``Subdivision of the Hierarchy of H-Colorable Graph Classes by Circulant Graphs'',; Workshop on Graphs and Combinatorial Optimization (CTW04), pp.232--236, May 2004.; >> Abstract

id=2004-07: K. Iwama, S. Miyazaki, and K. Okamoto,; ``A $(2 - c \log N / N)$-Approximation Algorithm for the Stable Marriage Problem'',; Proc. the 9th Scandinavian Workshop on Algorithm Theory (SWAT 2004), LNCS 3111, pp.349--361, Jul. 2004.; >> Abstract

id=2004-08: K. Iwama,; ``Automated competitive analysis of online algorithms'',; Workshop on On-Line Algorithms (OLA 2004), Jul. 2004.; >> Abstract

id=2004-15: T. Imamura, K. Iwama, and T. Tsukiji,; ``Approximated Vertex Cover for Graphs with Perfect Matchings'',; Proc. 10th Annual International Conference (COCOON 2004), pp.132--142, Aug. 2004.; >> Abstract

id=2004-16: H. Ito, K. Iwama, and T. Tamura,; ``Imperfectness of Data for STS-Based Physical Mapping'',; Proc. the 3rd IFIP International Conference on Theoretical Computer Science (TCS2004), pp.279--292, Aug. 2004.; >> Abstract

id=2004-17: A. Kawachi, H. Kobayashi, T. Koshiba, and Rudy Raymond H.P.,; ``Universal Test for Quantum One-Way Permutations'',; Proc. the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), LNCS 3153, pp.839--850, Aug. 2004.; >> Abstract

id=2004-20: H. Ito,; ``Three equivalent partial orders on graphs with real edge-weights drawn on a convex polygon'',; Proc. the Japan Conference on Discrete and Computational Geometry (JCDCG2004), LNCS 3742, pp.123--130, Oct. 2004.; >> Abstract

id=2004-21: N. Doi, T. Horiyama, M. Nakanishi, and S. Kimura,; ``An Optimization Method in Floating-point to Fixed-point Conversion using Positive and Negative Error Analysis and Sharing of Operations'',; Proc. the 12th Workshop on Synthesis And System Integration of Mixed Information Technologies (SASIMI 2004), pp.466--471, Oct. 2004.

id=2004-22: K. Iwama, and A. Kawachi,; ``Approximated Two Choices in Randomized Load Balancing'',; Proc. the 15th Annual International Symposium on Algorithms and Computation (ISAAC 2004), LNCS 3341, pp.545--557, Dec. 2004.; >> Abstract

id=2004-26: T. Imamura, and K. Iwama,; ``Approximating Vertex Cover on Dense Graphs'',; Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp., Jan. 2005.; >> Abstract

id=2004-28: H. Fujiwara, and K. Iwama,; ``Average-Case Competitive Analyses for Ski-Rental Problems'',; Dagstuhl Seminar 05031 (Algorithms for Optimization with Incomplete Information), Jan. 2005.; >> Abstract

id=2004-29: K. Iwama, A. Kawachi, Rudy Raymond H.P., and S. Yamashita,; ``Robust Quantum Algorithms for Oracle Indentification'',; Proc. 8th workshop on Quantum Information Processing (QIP 2005), Jan. 2005.; >> Abstract

[ 国内発表 ]

id=2004-01: 岡本和也, 宮崎修一, 岩間一雄,; ``局所探索法による安定結婚問題の近似'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.104, no.16, COMP2004-8, pp.53--60, 2004年 4月.; >> Abstract

id=2004-06: 中塚裕之, 堀山貴史, 岩間一雄,; ``逆算法に基づく詰将棋の列挙'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.104, COMP2004-20, pp.11--18, 2004年 6月.; >> Abstract

id=2004-09: 河内亮周, 山下茂, 岩間一雄,; ``オラクル同定問題に対する頑健な量子アルゴリズム'',; 情報処理学会アルゴリズム研究会, 情処研報, 2004-AL-96, 2004-AL-96, pp.1--8, 2004年 7月.; >> Abstract

id=2004-10: J. Kawahara, T. Horiyama, K. Iwama,; ``Automated Proof of Competitive Ratios for Online Problems'',; 夏のLAシンポジウム, pp.22.1--22.4, 2004年 7月.; >> Abstract

id=2004-11: A. Kawachi, H. Kobayashi, T. Koshiba, and Rudy Raymond H.P.,; ``Universal Test for Quantum One-Way Permutations'',; 夏のLAシンポジウム, pp.23.1--23.12, Jul. 2004.; >> Abstract

id=2004-12: X. Han, K. Iwama, and G. Zhang,; ``On-line Removable Square Packing'',; 夏のLAシンポジウム, Jul. 2004.; >> Abstract

id=2004-13: 土井伸洋, 中西正樹, 堀山貴史, 木村晋二,; ``浮動小数点演算での誤差の増減を考慮した変数のビット長最適化'',; 情報処理学会 DA シンポジウム 2004 論文集, B2-2, pp.85--90, 2004年 7月.

id=2004-18: 土井伸洋, 堀山貴史, 中西正樹, 木村晋二,; ``負方向への誤差を考慮した高位合成向けビット長最適化手法'',; 電子情報通信学会ソサエティ大会講演論文集, AS-3-1, 2004年 9月.

id=2004-27: 田村武幸, 伊藤大雄, 岩間一雄,; ``遺伝的な距離に基づいた家系図推定問題'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.104, no.642, pp.33--39, 2005年 1月.; >> Abstract

id=2004-30: Y. Hanatani, T. Horiyama, and K. Iwama,; ``Haj\'os Calculus on Planar Graphs'',; 冬のLAシンポジウム, pp.3.1--3.4, Feb. 2005.; >> Abstract

id=2004-33: 土井伸洋, 堀山貴史, 中西正樹, 木村晋二,; ``非線形計画法と整数解の探索に基づく高位合成向けビット長最適化'',; 情報処理学会, システムLSI設計技術研究会, 2005-SLDM-119(23), pp.133--138, 2005年 3月.

[ 解説 ]

id=2004-32: 宮崎修一,; ``安定結婚問題'',; 電子情報通信学会誌, vol.88, no.3, pp.195--199, 2005年 3月.; >> Abstract

Abstract

id=2004-01: 安定結婚問題の例題では、各個人の希望リストは異性全員を含み、完全に順位付けされている必要がある。しかし、実世界での応用を考えると、ペアになりたくない相手は希望リストに書かない不完全リストや、好みが同じ程度の人は優劣をつけなくて良い同順位リストという 2つの自然な拡張が考えられる。どちらか一方の拡張のみを許した問題は多項式時間で解くことができるが、両方の拡張を許した場合、最大サイズの安定マッチングを見つける問題は NP困難になることが知られている。任意の2つの安定マッチングのサイズは最大でも2倍しか異ならないということは簡単にわかるため、近似度が2の近似アルゴリズムは自明である。 2よりも良い近似度を実現する近似アルゴリズムを与える結果はいくつか知られているが、それらは、例えば同順位の長さや出現数などの制限を加えられた下でのものだけである。現在まで一般的な入力に対し、近似度が2未満となる近似アルゴリズムは知られていない。本論文では、一般的な例題に対し、近似度が2未満となる非自明な結果を初めて示した。我々のアルゴリズムの近似度は$2-c\frac{\log N}{N}$である。 (ここで、$c$は任意の正定数で、$N$は入力中の男性の数である。)

id=2004-02: $H$-coloring problem is a coloring problem with restrictions such that some pairs of colors cannot be used for adjacent vertices, where $H$ is a graph representing the restrictions of colors. We deal with the case that $H$ is the complement graph $\overline{C_{2p+1}}$ of a cycle of odd order $2p+1$. This paper presents the following results: (1) chordal graphs and internally maximal planar graphs are $\overline{C_{2p+1}}$-colorable if and only if they are $p$-colorable ($p \geq 2$), (2) $\overline{C_7}$-coloring problem on planar graphs is NP-complete, and (3) there exists a class that includes infinitely many $\overline{C_7}$-colorable but non-3-colorable planar graphs.

id=2004-03: For any integer $p \geq 2$, $p$-colorable graphs are $\overline{C_{2p+1}}$-colorable and $\overline{C_{2p+1}}$-colorable graphs are $p+1$-colorable, where $\overline{C_{2p+1}}$ is the complement graph of a cycle of order $2p+1$. The converse statements are however incorrect. This paper presents that the above inclusion can be subdivided by a subset of circulant graphs $H(n, k)~(n, k \in \mbox{\boldmath $N$},~k \leq \lfloor n/2 \rfloor)$. The subdivided hierarchy of inclusion contains the well-known inclusion of $C_{2p+1}$-colorable graphs. Moreover, we prove some NP-complete problems for planar $H(n, k)$-colorings, including the $\overline{C_5}$-coloring.

id=2004-04: The online CNN Problem had no known competitive algorithms for a long time. Sitters, Stougie and de Paepe showed that there exists a competitive online algorithm for this problem. However, both their algorithm and analysis are quite complicated, and above all, their upper bound for the competitive ratio is $10^5$. In this paper, we examine why this problem seems so difficult. To this end we introduce a nontrivial restriction, orthogonality, against this problem and show that it decreases the competitive ratio dramatically, down to at most 9.

id=2004-05: In the CNN problem, a ``scene'' appears on the two-dimensional plane, at different positions sequentially, and a ``camera crew'' has to shoot the scene whenever it appears. If a scene appears at some position, the camera crew does not have to move to the position exactly, but has only to move to a point that lies in the same horizontal or vertical line with the scene. Namely it is enough to move either to the same row or to the same column. The goal is to minimize the total moving distance of the camera crew. This problem has been quite popular in the last decade but it is still open whether or not there is a competitive algorithm, i.e., an algorithm with competitive ratio bounded by a constant. In this paper we study this problem under a natural restriction that the server can move only along the $X$-axis and the $Y$-axis. It is shown that there exists a competitive algorithm for this restricted version, namely there is an online algorithm for this ``axis-bound CNN'' with competitive ratio $9.0$.

id=2004-06: 近年の計算機の高速化や大容量化、洗練されたアルゴリズム設計法の発展により、与えられた条件を満たす解を1つだけでなくすべて列挙することが、実用上要請されるようになってきている。本研究では、逆算法による詰将棋の列挙アルゴリズムを提案する。従来手法では、詰将棋となる可能性のある局面を数え挙げ、これを順に詰将棋解答プログラムに解かせてそれぞれが詰将棋として成立していることを確認しているため、実行時間が長くなりがちである。本手法では、逆算法により詰め手数の少ないものから順に詰将棋を列挙することで、詰将棋解答プログラムを用いることなく、与えられた条件下で可能な詰将棋を高速に列挙することができる。また、提案アルゴリズムをC言語で実装し、桂図式等の複数の条件において列挙を行う。生成可能なものをすべて数え挙げられるため、例えば桂図式は最長手数が9手である等、各図式の最長手数を証明したことになる。

id=2004-07: We propose an approximation algorithm for the problem of finding a maximum stable matching when both ties and unacceptable partners are allowed in preference lists. Our algorithm achieves the approximation ratio $2-c\frac{\log N}{N}$ for an arbitrarily positive constant $c$, where $N$ denotes the number of men in an input. This improves the trivial approximation ratio of two.

id=2004-08: The main objective of this paper is to present a rather general framework for automated competitive analysis, i.e., for using computers to prove a competitive ratio of online algorithms. As an example, we use the Exchangeable Online Knapsack problem and prove an upper bound of 1.3334 for its competitive ratio using our system. There are two features: (i) Our system automatically generates different "states" of the game, the entire size of which is usually much larger than the size of the algorithm description. (ii) For claiming a concrete value for the competitive ratio, our system can use formula expression or does not have to depend on numerical analysis. For this purpose our system includes Mathematica as a part of the system.

id=2004-09: オラクル同定問題とは $n$ビット入力$1$ビット出力のオラクルの集合$S=\{f_1,...,f_M\}$と $S$に属する未知のオラクル$f_i$が与えられたとき，未知のオラクル$f_i$を$S$の中から同定する問題であり，数多くの問題の一般化になっている．本稿では，与えられた未知のオラクルクエリーの結果が正しい値と誤った値が重ね合わせ状態として出力される場合のオラクル同定問題（但し，誤った計算結果が得られる確率は $1/2$より小さい定数確率，例えば$1/10$以下とする．）に対して以下を示す． (i)~与えられたオラクル集合のサイズが$N=2^n$の場合（すなわち$M=N$．），エラー付きオラクル同定問題をクエリー回数$O(\sqrt{N})$で少なくとも定数確率で解く量子アルゴリズムが構成できる． (ii)~与えられたオラクル集合のサイズが$N$の場合，各$x\in\{0,1\}^n$で$f_i(x)=1$を満たす$i$の数に関するパラメータ$K$に関してある条件を満たすとき，エラー付きオラクル同定問題をクエリー回数$O(\sqrt{N/K})$で少なくとも定数確率で解く量子アルゴリズムが構成できる．

id=2004-10: 種々のオンライン問題では、オンラインアルゴリズムを設計し、競合比を計算するが、しばしば場合分けが膨大な数に及ぶことがある。今回はそのような問題の代表としてオンラインナップザック問題を考える。オンラインナップザック問題はプレイヤはアイテムが一つずつ順番に与えられ、そのたびにそのアイテムをナップザックの中に入れるか捨てるかを決めるオンライン問題である。この問題の競合比上限を証明するとき、アイテムのサイズによる場合分けが20種類以上にも及ぶことが分かった[1]。そこで、この場合分けを計算機を用いて自動的に生成し、競合比の証明を行う。本稿では交換可能オンラインナップザック問題(EOK)での$k=2$の場合の上限が 1.3334であることを計算機を用いて証明を行った。

id=2004-11: The next bit test was introduced by Blum and Micali and proved by Yao to be a universal test for cryptographic pseudorandom generators. On the other hand, no universal test for the cryptographic one-wayness of functions (or permutations) is known, though the existence of cryptographic pseudorandom generators is equivalent to that of cryptographic one-way functions. In the quantum computation model, Kashefi, Nishimura and Vedral gave a sufficient condition of (cryptographic) quantum one-way permutations and conjectured that the condition would be necessary. In this paper, we relax their sufficient condition and give a new condition that is necessary and sufficient for quantum one-way permutations. Our condition can be regarded as a universal test for quantum one-way permutations, since our condition is described as a collection of stepwise tests similar to the next bit test for pseudorandom generators.

id=2004-12: In this paper, we consider an on-line square packing problem: Given a list of squares with side length of at most 1, we are asked to pack a subset of them, in an on-line manner and without any overlap, into a unit square bin so that the packed area (the total area of squares packed) is as large as possible. We assume that removal is allowed. It means that a packed square can be removed from the square bin. However, once a square is rejected or removed it will never been considered again. We first show a lower bound of 2.618 for any on-line algorithm. Then we propose an on-line algorithm based on partitioning the square bin into bricks and show a competitive ratio of 3. As a byproduct it is proved that any list of squares with total area no more than 1/3 can be on-line packed in a unit square, which improves the previous best known result by Januszewski and Lassak.

id=2004-14: We consider problems of reasoning with a knowledge-base, which is represented by an ordered binary decision diagram (OBDD), for two cases of general and Horn knowledge-bases. Our main results say that both finding a model of a knowledge-base and deducing from a knowledge-base can be done in linear time for a general knowledge-base, but that abduction is NP-complete even for a Horn knowledge-base. Then, we consider abduction when its assumption set consists of all propositional literals (i.e., an answer for a given query is allowed to include any positive literals), and show that it can be done in polynomial time if the knowledge-base is Horn, while it remains NP-complete for the general case. Some other solvable cases are also discussed.

id=2004-15: Chen and Kanj considered the Vertex Cover problem for graphs with perfect matchings (VC-PM). They showed that: (i) There is a reduction from general Vertex Cover to VC-PM, which guarantees that if one can achieve an approximation factor of less than two for VC-PM, then one can do so for general Vertex Cover as well. (ii) There is an algorithm for VC-PM whose approximation factor is given as $1.069 + 0.069d$ where $d$ is the average degree of the given graph. In this paper we improve (ii). Namely we give a new VC-PM algorithm which greatly outperforms the above one and its approximation factor is roughly $2 - \frac{6.74}{d+6.28}$. Our algorithm also works for graphs with ``large'' matchings although its approximation factor is degenerated.

id=2004-16: In the STS-based mapping, we are requested to obtain the correct order of probes in a DNA sequence from a given set of fragments or equivalently a hybridization matrix $A$. It is well-known that the problem is formulated as the combinatorial problem of obtaining a permutation of $A$'s columns so that the resulting matrix has the consecutive-one property. If the data (the hybridization matrix) is error free and includes enough information, then the above column order determines the correct order of the probes uniquely. Unfortunately this is no longer true if the data include errors, which has been one of the popular research targets in computational biology. Even if there is no error, ambiguities in the probe order may still remain. This in fact happens by the lack of some information of the data, but almost no further investigation was made previously. In this paper, we define a measure of such imperfectness of the data as a minimum amount of additional fragments which are needed to fix the probe order uniquely. Several polynomial-time algorithms to compute such additional fragments of minimum cost are presented.

id=2004-17: The next bit test was introduced by Blum and Micali and proved by Yao to be a universal test for cryptographic pseudorandom generators. On the other hand, no universal test for the cryptographic one-wayness of functions (or permutations) is known, though the existence of cryptographic pseudorandom generators is equivalent to that of cryptographic one-way functions. In the quantum computation model, Kashefi, Nishimura and Vedral gave a sufficient condition of (cryptographic) quantum one-way permutations and conjectured that the condition would be necessary. In this paper, we relax their sufficient condition and give a new condition that is necessary and sufficient for quantum one-way permutations. Our condition can be regarded as a universal test for quantum one-way permutations, since our condition is described as a collection of stepwise tests similar to the next bit test for pseudorandom generators.

id=2004-19: While the original stable marriage problem requires all participants to rank all members of the opposite sex in a strict order, two natural variations are to allow for incomplete preference lists and ties in the preferences. Either variation is polynomially solvable, but it has recently been shown to be NP-hard to find a maximum cardinality stable matching when both of the variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, an approximation algorithm with a factor two is trivial. In this paper, we give a randomized approximation algorithm RandBrk and show that its expected approximation ratio is at most $10/7 (< 1.4286)$ for a restricted but still NP-hard case, where ties occur in only men's lists, each man writes at most one tie, and the length of ties is two. We also show that our analysis is nearly tight by giving a lower bound $32/23 (> 1.3913)$ for RandBrk. Furthermore, we show that these restrictions except for the last one can be removed without increasing the approximation ratio too much.

id=2004-20: Three partial orders, cut-size order, length order, and operation order, defined between labeled multigraphs with the same order are known to be equivalent. This paper extends the result on edge-capacitated graphs, where the capacities are real numbers, and it presents a proof of the equivalence of the three relations. From this proof, it is also shown that we can determine whether or not a given graph precedes another given graph in polynomial time.

id=2004-22: This paper studies the maximum load in the {\it approximated} $d$-choice balls-and-bins game where the current load of each bin is available only approximately. In the model of this game, we have $r$ thresholds $T_1,...,T_r$ $(0 < T_1 < \cdots < T_r)$ for an integer $r$ $(\geq 1)$. For each ball, we select $d$ bins and put the ball into the bin of the lowest range, i.e., the bin of load $i$ such that $T_k \leq i \leq T_{k+1}-1$ and no other selected bin has height less than $T_k$. If there are two or more bins in the lowest range (i.e., their height is between $T_k$ and $T_{k+1}-1$), then we assume that those bins cannot be distinguished and so one of them is selected uniformly at random. We then estimate the maximum load for $n$ balls and $n$ bins in this game. In particular, when we put the $r$ thresholds at a regular interval of an appropriate $\Delta$, i.e., $T_r-T_{r-1} = \cdots = T_2 - T_1 = T_1 = \Delta$, the maximum load $L(r)$ is given as $(r + O(1)) \sqrt[r+1]{\frac{r+1}{(d-1)^r} \ln n / \ln\left( \frac{r+1}{(d-1)^r} \ln n \right) }.$ The bound is also described as $L(\Delta) \leq \{(1+o(1))\ln\ln n+O(1)\}\Delta/\ln((d-1)\Delta)$ using parameter $\Delta$. Thus, if $\Delta$ is a constant, this bound matches the (tight) bound in the original $d$-choice model given by Azar et al., within a constant factor. The bound is also tight within a constant factor when $r=1$.

id=2004-23: In a recent communication network, some mirror servers that provide the same service as an original server are often used. From the view of the network reliability, it is important that a client can access to at least one of the original or its mirror servers, even if some links or nodes fail. Therefore, it is necessary to design a network so that it ensures some independent routes between a client and a set of servers that provide the same service. When a communication network is modeled by a graph, the connectivity between a client and some mirror servers can be measured by NA(Node-to-Area)-edge(resp. vertex)-connectivity between a vertex and a vertex subset (an area), which is equal to the number of edge(resp. vertex)-independent paths between a vertex and an area. In this paper, we focus on the network design problem to increase the reliability of a current network by adding the smallest number of links. This problem can be formulated as the problem of augmenting a graph by adding the smallest number of new edges to meet NA-edge(vertex)-connectivity requirement. First, we prove the NP-completeness of the problem to determine whether a graph can be 1-NA-edge-connected by adding the given number or less of edges. Next, we show that the problem of augmenting a graph to be 2-NA-edge-connected by adding the smallest edges can be solved in polynomial time.

id=2004-24: It is known that the original Grover Search (GS) can be modified to use a general value for the phase $\theta$ of the diffusion transform. Then, if the number of answers is relatively large, this modified GS can find one of the answers with probability one in a single iteration. However, such a quick and error-free GS can only be possible if we can initially adjust the value of $\theta$ correctly against the number of answers, and this seems very hard in usual occasions. A natural question now arises: Can we enjoy a merit even if GS is used without such an adjustment? In this paper, we give a positive answer using the balls-and-bins game in which the random sampling of bins is replaced by the quantum sampling, i.e., a single round of modified GS. It is shown that by using the quantum sampling: (i) The maximum load can be improved quadratically for the static model of the game and this improvement is optimal. (ii) That is also improved to $O(1)$ for the continuous model if we have a certain knowledge about the total number of balls in the bins after the system becomes stable.

id=2004-25: 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. (The table-size is later improved to $O(n^{1/2}\log^{3/2} n)$.) 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=2004-26: Although many problems in MAX-SNP admit a PTAS for dense graphs, that is not the case for Vertex Cover, which is MAX-SNP hard even for dense graphs. This paper presents a randomized approximation algorithm for Vertex Cover on dense graphs, i.e., graphs whose average degree d is $\Omega(n)$. (i) Our algorithm improves the best-known bound for the approximation factor by Karpinski and Zelikovsky. For example, our bound is $\frac{2}{1+ \frac{d}{2\Delta}}$ for dense graphs such that $|E| \le \Delta(n - \Delta)$ where $\Delta$ is the maximum degree. The improvement is especially large when $d \approx \Delta$; if $d \ge \frac{2}{3}\Delta$ for instance, our bound is at most 1.5 while the previous bound approaches to 2.0 as $\frac{n}{\Delta}$ increases. (ii) It achieves the same factor for a wider range of graphs, i.e., for the graphs whose $\Delta$ is $\Omega(n\frac{log log n}{log n} )$. (iii) It is probably optimal in the sense that if we can achieve a better approximation factor by $\delta > 0$ for the above range of graphs, then we can achieve a factor of $2 - \delta$ for general graphs.

id=2004-27: 進化系統樹とは地球上の生物が、共通の祖先から進化したと考えた時の、種間の進化的な関係を表現した木構造である。遺伝的な情報から進化系統樹を推定する方法に対する研究はさかんに行われてきた。また系統樹の一部に修正を加えたデータ構造を推定する研究も近年行われきている。これに対し、家系図は進化系統樹をさらに詳しくしたものと考えることができる。進化系統樹をグラフで表現すれば有向木になるのに対し、家系図は入次数が２以下の非閉路的有向グラフとなる。本稿では、与えられた２節点間の遺伝的距離を満足する家系図を全て列挙する問題を考え、所望の家系図の全てが、節点数を増やすことなく一つの有向グラフで表現できることを示し、それを得る$O(n^3)$ 時間アルゴリズムを与える。

id=2004-28: 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=2004-29: The oracle identification problem (OIP) was introduced by Ambainis et. al., which is given as a set $S$ of $M$ oracles and a hidden oracle $f$. Our task is to figure out which oracle in $S$ is equal to the hidden $f$ by doing queries to $f$. OIP includes several problems such as Grover Search as special cases. In this paper, we design {\it robust} algorithms, i.e., those which are tolerant against noisy oracles, for OIP. Our results include: ($i$) For any oracle set $S$ such that $|S|$ is polynomial in $N$, $O(\sqrt{N})$ queries are enough to identify the hidden oracle, which is obviously optimal since this OIP includes Grover Search as a special case. ($ii$) For the case that $|S| \le 2^{N^d} (d < 1)$, we design an algorithm whose query complexity is $O(\sqrt{N \log M/ \log N})$ and matches the lower bound proved before. ($iii$) We can furthermore design a robust algorithm whose complexity changes smoothly between the complexity of ($ii$) and the complexity of recovering all information about the hidden oracle whose complexity is O(N) as showed by Buhrman et. al. Thus our new algorithms are not only robust but also their query complexities are even better than the previous noiseless case.

id=2004-30: The Haj\'os calculus is a nondeterministic procedure which generates the class of non-3-colorable graphs. Unless NP~$\neq$~co-NP, there must exist graphs which need exponential steps to be constructed in the Haj\'os calculus, however it is not known. In this paper, we propose new systems of graph calculus which generate the class of non-3-colorable planar graphs and show its upper bound.

id=2004-31: 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=2004-32: 安定結婚問題は二部グラフにおけるマッチング問題の一種である．複数の男女がおり，各人は異性を自分の好みで順序づけした希望リストを持っている．その希望リストに基づいて「安定性」を満たすマッチング(結婚)を求めるのが，安定結婚問題である．この問題は，アメリカの研修医配属への応用が有名であるが，近年日本の研修医配属でも利用し始められた．本稿では，安定結婚問題の基本的性質や応用例を紹介する．

id=2004-34: For networks employing shortest-path routing, we introduce a new recovery scheme that needs only one extra backup routing table. By precomputing this backup table, the network recovers from any single link-failure immediately after the failure occurs. To compute the backup routing table for this scheme, we use the almost-linear-time algorithm to solve {r, v}-problem, which is a variation of the best swap problem, presented by Nardelli, et al. We further show that the same solution can be computed in exactly linear time if the underlying graph is unweighted.

岩間研究室 発表論文

2004年度

[ 論文誌 ]

[ 国際会議 ]

[ 国内発表 ]

[ 解説 ]

Abstract

岩間研究室発表論文