# 岩間研究室 発表論文

## [ 論文誌 ]

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

局所探索法による安定結婚問題の近似'',

>> Abstract
id=2004-06

逆算法に基づく詰将棋の列挙'',

>> Abstract
id=2004-09

オラクル同定問題に対する頑健な量子アルゴリズム'',

>> Abstract
id=2004-10
J. Kawahara, T. Horiyama, K. Iwama,
Automated Proof of Competitive Ratios for Online Problems'',

>> Abstract
id=2004-11
A. Kawachi, H. Kobayashi, T. Koshiba, and Rudy Raymond H.P.,
Universal Test for Quantum One-Way Permutations'',

>> Abstract
id=2004-12
X. Han, K. Iwama, and G. Zhang,
On-line Removable Square Packing'',

>> Abstract
id=2004-13

浮動小数点演算での誤差の増減を考慮した変数のビット長最適化'',

id=2004-18

負方向への誤差を考慮した高位合成向けビット長最適化手法'',

id=2004-27

遺伝的な距離に基づいた家系図推定問題'',

>> Abstract
id=2004-30
Y. Hanatani, T. Horiyama, and K. Iwama,
Haj\'os Calculus on Planar Graphs'',

>> Abstract
id=2004-33

非線形計画法と整数解の探索に基づく高位合成向けビット長最適化'',

## [ 解説 ]

id=2004-32

安定結婚問題'',

>> Abstract

## Abstract

id=2004-01

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

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

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

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.