# 岩間研究室 発表論文

## [ 論文誌 ]

id=2005-28
M. Adcock, R. Cleve, K. Iwama, R. Raymond, and S. Yamashita,
Quantum Lower Bounds for the Goldreich-Levin Problem'',
Information Processing Letters, vol.97, no.5, pp.208--211, Mar. 2006.

## [ 国際会議 ]

id=2005-03
Y. Hanatani, T. Horiyama, and K. Iwama,
Haj\'os Calculus on Planar Graphs'',
Proc. the 4th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pp.76--83, Jun. 2005.

>> Abstract
id=2005-04
H. Ito, G. Nakamura, and S. Takata,
Chomp with Poison-Strewn Chocolates'',
Proc. the 4th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pp.336--343, Jun. 2005.
id=2005-09
W. W. Bein, K. Iwama, L. L. Larmore, and J. Noga,
The Delayed k-Server Problem'',
Proc. the 15th International Symposium on Fundamentals of Computation Theory (FCT 2005), pp.281--292, Aug. 2005.

>> Abstract
id=2005-10
K. Iwama, A. Lingas, and M. Okita,
Max-stretch Reduction for Tree Spanners'',
Proc. the 9th International Workshopon Algorithms and Data Structures (WADS 2005), pp.122--133, Aug. 2005.

>> Abstract
id=2005-12
X. Han, K. Iwama, and G. Zhang,
On-line Removable Square Packing'',
Proc. the 3rd International Workshop on Approximation and Online Algorithms (WAOA 2005), LNCS 3879, pp.216--229, Oct. 2005.

>> Abstract
id=2005-13
H. Ito, K. Iwama, and T. Osumi,
Linear-Time Enumeration of Isolated Cliques'',
Proc. the 13th Annual European Symposium on Algorithms (ESA 2005), LNCS 3669, pp.119--130, Oct. 2005.

>> Abstract
id=2005-16
J. Akiyama, H. Fukuda, H. Ito, and G. Nakamura,
Infinite Series of Generalized Gospher Space Filling Curves'',
Abstracts of the China-Japan Conference on Discrete Geometry, Combinatorics, and Graph Theory (CJCDGCGT) 2005, pp.6--8, Nov. 2005.
id=2005-17
H. Ito,
Transformation of Simple Graphs Preserving Cut-Size Order and Their Simpleness'',
Abstracts of the China-Japan Conference on Discrete Geometry, Combinatorics, and Graph Theory (CJCDGCGT) 2005, pp.12--14, Nov. 2005.
id=2005-18
K. Iwama, S. Miyazaki, and N. Yamauchi,
A $(2-c 1 / \sqrt{N})$-Approximation Algorithm for the Stable Marriage Problem'',
Proc. the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005), LNCS 3827, pp.902--914, Dec. 2005.

>> Abstract
id=2005-20
M. Hayashi, K. Iwama, H. Nishimura, R. Raymond, and S. Yamashita,
Quantum Network Coding'',
Proc. the 9th Workshop on Quantum Information Processing (QIP2006), Jan. 2006.

>> Abstract
id=2005-21
※ S. Miyazaki, and Y. Okabe,
Cheat-proof Serverless Network Games'',
Proc. the 4th International Symposium on Computing and Media Studies, pp.94--101, Jan. 2006.

>> Abstract
id=2005-23
H. Nishimura,
Random Access Coding and Its Application'',
Proc. workshop on Theory of Quantum Computation, Communcation, and Cryptography (TQC2006), pp.6--7, Feb. 2006.

>> Abstract
id=2005-25
S. Albers, and H. Fujiwara,
Energy-Efficient Algorithms for Flow Time Minimization'',
Proc. the 23rd International Symposium on Theoretical Aspects of Computer Science (STACS 2006), LNCS 3884, pp.621--633, Feb. 2006.

>> Abstract

## [ 国内発表 ]

id=2005-01

入札額の範囲が制限された正直なオークション'',

>> Abstract
id=2005-02

安定結婚問題に対する局所探索近似アルゴリズムの改良'',

>> Abstract
id=2005-05
※ 小林浩二, 宮崎修一, 岡部寿男,
共有メモリ型スイッチにおけるオンラインバッファ管理アルゴリズムの競合比の改良'',

>> Abstract
id=2005-06

最大被覆供給点配置問題に関する考察'',

>> Abstract
id=2005-07

否定数を$\log (n+1)$に限定した回路計算量の下界について'',

>> Abstract
id=2005-11

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

>> Abstract
id=2005-14
T. Horiyama, K. Iwama, and J. Kawahara,
Automated Competitive Analysis of Online Problems'',

>> Abstract
id=2005-15
※ 宮崎修一, 久保浩史, 高見好男, 四方敏明, 櫻井恒正, 山元伸幸, 河野典, 江原康生, 高倉弘喜, 沢田篤史, 中村素典, 岡部寿男, 北野正雄,
KUINS接続機器登録データベースの概要'',

id=2005-19
K. Iwama, H. Nishimura, R. Raymond, and S. Yamashita,
Transmitting Classical Information on the Quantum Network Efficiently'',

>> Abstract
id=2005-22

二段組合せ回路の最大動作率について'',

>> Abstract
id=2005-24
M. Hayashi, K. Iwama, H. Nishimura, R. Raymond, and S. Yamashita,
Efficient Transmission of the Information on the Quantum Network'',

id=2005-26
K. Sugihara, and H. Ito,
Maximum-Cover Source-Location Problem with Objective Edge-Connectivity Three'',

>> Abstract
id=2005-27
X. Han, K. Iwama, and G. Zhang,
Packing Squares with Profits into a Rectangle'',

id=2005-29

毒まみれ半順序付き集合ゲームの必勝法'',

>> Abstract
id=2005-30
K. Iwama, and S. Tamaki,
Increasing the Success Probability of PPSZ-type Satisfiability Testing'',

>> Abstract

## Abstract

id=2005-01
1回入札，秘密入札(入札額が他人には分からない入札)の 正直なオークション(truthful auction)を扱う． 正直なオークションでは，正直に入札すること， すなわち自分にとっての真の利用価値を自分の入札値とすることで， 最良の利得を得ることが保証される． 正直なオークションを実現するアルゴリズムの性能評価には競合比が用いられ， これまでに下界が2.42であることが知られている． また，COREアルゴリズムが提案されており，競合比3.39を達成している． 本報告では，入札額の最大値と最小値の比が高々$r$倍以内である時に， 競合比$\ln r + 1$を達成するオークションアルゴリズムを提案する． 最初に，基本となるアルゴリズムとして，他の入札者の最低入札額を 提示額とする最低入札額オークションを示す． このアルゴリズムを拡張することで， 最低入札額またはその定数倍の複数の提示額をもつオークションを提案する． 提示額の種類を増化させることで競合比は改善され， 確率分布により提示額を決定することで競合比$\ln r + 1$を達成する．
id=2005-02

id=2005-03
The Haj\'os calculus is a nondeterministic procedure which generates the class of non-3-colorable graphs. If all non-3-colorable graphs can be constructed in polynomial steps by the calculus, NP = co-NP holds. Up to date, however, it remains open whether there exists a family of graphs that can be generated in polynomial steps. To attack this problem, we propose two graph calculi PHC and PHC$^*$ that generate non-3-colorable planar graphs, where intermediate graphs in the calculi are also restricted to be planar. Then we prove that PHC and PHC$^*$ are sound and complete. We also show that PHC$^*$ can polynomially simulate PHC.
id=2005-05
オンラインバッファ管理問題は， 近年のネットワーク運用における主要な論点となっている QoS (Quality of Service) 保証実現のための，スイッチなどの キュー管理をオンライン問題として定式化した問題であり， 様々なモデルが考案されている．本論文ではその中の1つである 共有メモリ型スイッチを扱ったモデルを取り上げる． 我々は，アルゴリズム Longest Queue Policy ($LQD$) の競合比の既知の上限を $2 - 1/N$ に改良した．ここで，$N$はスイッチの出力ポート数である．
id=2005-06

id=2005-07

id=2005-09
We introduce a new version of the server problem: the delayed server problem. In this problem, once a server moves to serve a request, it must wait for one round to move again, but could serve a repeated request to the same point. We show that the delayed k-server problem is equivalent to the $(k-1)$-server problem in the uniform case, but not in general.
id=2005-10
A tree $t$-spanner $T$ of a graph $G$ is a spanning tree of $G$ whose max-stretch is $t$, i.e., the distance between any two vertices in $T$ is at most $t$ times their distance in $G$. If $G$ has a tree $t$-spanner but not a tree $(t-1)$-spanner, then $G$ is said to have max-stretch of $t$. In this paper, we study the Max-Stretch Reduction Problem: for an unweighted graph $G = (V,E)$, find a set of edges not in $E$ originally whose insertion into $G$ can decrease the max-stretch of $G$. Our results are as follows: (i) For a ring graph, we give a linear-time algorithm which inserts $k$ edges improving the max-stretch optimally. (ii) For a grid graph, we give a nearly optimal max-stretch reduction algorithm which preserves the structure of the grid. (iii) In the general case, we show that it is NP-hard to decide, for a given graph $G$ and its spanning tree of max-stretch $t$, whether or not one-edge insertion can decrease the max-stretch to $t-1$. (iv) Finally, we show that the max-stretch of an arbitrary graph on $n$ vertices can be reduced to $s' \geq 2$ by inserting $O(n/s')$ edges, which can be determined in linear time, and observe that this number of edges is optimal up to a constant.
id=2005-11

id=2005-12
The online removable square packing problem is a two-dimensional version of the online removable Knapsack problem. For a sequence of squares with side length at most 1, we are requested to pack a subset of them into a unit square in an online fashion where the online player can decide whether to take the current square or not and which squares currently in the unit square to remove. The goal is to maximize the total packed area. Our results include: (i) Any online algorithm cannot achieve a better competitive ratio than 2.618. (ii) The matching upper bound is achieved by a relatively simple online algorithm if repacking is allowed. (iii) Without repacking, we can achieve an upper bound of 3.0 by using the concept of bricks by Januszewski and Lassak. (iv) The offline version of the problem admits a PTAS.
id=2005-13
For a given graph G of n vertices and m edges, a clique S of size k is said to be c-isolated if there are at most ck outgoing edges from S. It is shown that this parameter c is an interesting measure which governs the complexity of finding cliques. In particular, if c is a constant, then we can enumerate all c-isolated maximal cliques in linear time, and if c = O(log n), then we can enumerate all c-isolated maximal cliques in polynomial time. Note that there is a graph which has a superlinear number of c-isolated cliques if c is not a constant, and there is a graph which has a superpolynomial number of c-isolated cliques if c = ω(log n). In this sense our algorithm is optimal for the linear-time and polynomial-time enumeration of c-isolated cliques.
id=2005-14
In this paper we study the 2-Bin Exchangeable Online Knapsack Problem (2EOK) which is an extension of the 2-Bin Removable Online Knapsack Problem. We prove an optimal upper bound of $1/t$ for the competitive ratio of 2EOK, where $t$ is a real root of $4x^3 + 5x^2 - x - 4 = 0$ ($t \approx 0.76850$ and $1/t \approx 1.3012$). To prove this result, we made a full use of computer programs as follows: For the algorithm we wish to prove the upper bound, we first construct an equivalent finite state diagram with about 300 states. Then for each state we generate a finite set of inequalities such that the competitive ratio at that state is at most $1/t$ if the set of inequalities do not have a real solution. The latter can be checked by Mathematica. The number of inequalities generated was approximately 600 in total, and our computation time was 30 minutes using Athlon XP 2600+.
id=2005-18
We consider the problem of finding a stable matching of maximum size when both ties and unacceptable partners are allowed in preference lists. This problem is NP-hard and the current best known approximation algorithm achieves the approximation ratio $2-c\frac{\log N}{N}$, where $c$ is an arbitrary positive constant and $N$ is the number of men in an input. In this paper, we improve the ratio to $2-c\frac{1}{\sqrt{N}}$, where $c$ is a constant such that $c \leq \frac{1}{4 \sqrt{6}}$.
id=2005-19
The question in this paper is whether the quantum random access (QRA) coding, given by Ambainis et al., on the {\it network} is possible. This question is motivated by the network coding introduced by Ahlswede et al., which enables us to send classical information much more efficiently on the network by coding at intermediate nodes. We demonstrate that quantum network coding is possible for the QRA coding, by using a simple network model called the Butterfly network. In this network, there are two flow paths, $s_1$ to $t_1$ and $s_2$ to $t_2$, which shares a single bottleneck channel of capacity one. In the classical case, we can send two bits simultaneously, one for each path, in spite of the bottleneck. However, the quantum case makes this bottleneck much more severe than in the classical case because of the non-orthogonality of quantum states. We resolve this bottleneck and design a protocol which can send two classical bits from $s_1$ to $t_1$ (similarly from $s_2$ to $t_2$) but only one of them should be recovered.
id=2005-20
Since quantum information is continuous, its handling is sometimes surprisingly harder than the classical counterpart. A typical example is cloning; making a copy of digital information is straightforward but it is not possible exactly for quantum information. The question in this talk is whether or not "quantum" network coding is possible. Its classical counterpart is another good example to show that digital information flow can be done much more efficiently than conventional (say, liquid) flow. Our answer to the question is similar to the case of cloning, namely, it is shown that quantum network coding is possible if approximation is allowed, by using a simple network model called Butterfly. In this network, there are two flow paths, s_1 to t_1 and s_2 to t_2, which shares a single bottleneck channel of capacity one. In the classical case, we can send two bits simultaneously, one for each path, in spite of the bottleneck. Our results for quantum network coding include: (i) We can send any quantum state |psi_1> from s_1 to t_1 and |psi_2> from s_2 to t_2 simultaneously with a fidelity strictly greater than 1/2. (ii) If one of |psi_1> and |psi_2> is classical, then the fidelity can be improved to 2/3. (iii) Similar improvement is also possible if |psi_1> and |psi_2> are restricted to only a finite number of (previously known) states. This allows us to design an interesting protocol which can send two classical bits from s_1 to t_1 (similarly from s_2 to t_2) but only one of them should be recovered.
id=2005-21
We consider playing online games on peer-to-peer networks, without assuming servers that control the execution of game. In such an environment, players may cheat the opponent by, for example, replacing the cards in hands illegally. The aim of this paper is to examine a possibility of excluding such cheatings. We show that by employing cryptographic techniques such as multi-party protocols, we can exclude some type of cheatings in some level. Finally, based on our discussion, we implement a cheat-proof network Gunjin-Shogi'', which is a kind of Japanese chess.
id=2005-22

id=2005-23
Quantum information theory says us that one quantum bit (qubit) has only the amount of one bit information from the sender to the receiver. On the contrary, how is the case where the receiver wants one of the bits the sender has? Ambainis et al. explored what can be done for this case by quantum information processing, which is called the quantum random access coding. This work reviews the study of quantum random access coding and its applications.
id=2005-25
We study scheduling problems in battery-operated computing devices, aiming at schedules with low total energy consumption. While most of the previous work has focused on finding feasible schedules in deadline-based settings, in this paper we are interested in schedules that guarantee good response times. More specifically, our goal is to schedule a sequence of jobs on a variable speed processor so as to minimize the total cost consisting of the power consumption and the total flow time of all the jobs. We first show that when the amount of work, for any job, may take an arbitrary value, then no online algorithm can achieve a constant competitive ratio. Therefore, most of the paper is concerned with unit-size jobs. We devise a deterministic constant competitive online algorithm and show that the offline problem can be solved in polynomial time.
id=2005-26
Given a graph $G=(V,E)$, a set of vertices $S\subseteq V$ covers a vertex $v\in V$ if the edge-connectivity between $S$ and $v$ is at least a given number $k$. Vertices in $S$ are called sources. The maximum-cover source-location problem, which is a variation of the source location problem, is to find a source set $S$ with a given size at most $p$, maximizing the sum of the weight of vertices covered by $S$. In this paper, we show a polynomial-time algorithm for this problem in the case of $k=3$ when a vertex-weighted and edge-capacitated undirected graph is input.
id=2005-29

id=2005-30
Recently, [Iwama, Tamaki, SODA04] gave a new worst-case upper bound for 3SAT by modifying the PPSZ-type algorithm in [Paturi et. al., FOCS98] by making use of the local-search-type one in [Schoning, Algorithmica 02]. We propose a different kind of modification in this paper. Recall that the analysis of the first algorithm (denoted by \textbf{PPSZ}) assumes that each bit of the initial assignment coincides that of a satisfying assignment with probability one half. Our idea is that if we can increase this probability, i.e., if we can use a better'' initial assignment, then the success probability of \textbf{PPSZ} should increase. To get this better assignment we use the second algorithm (denoted by \textbf{SCH}). Note that the local search starts with a random assignment and gradually approaches to a satisfying assignment $z$. In the middle of this process, there should be the moment that the current assignment $a^*$ is close to $z$ and to use \textbf{PPSZ} with this assignment $a^*$ has a better success probability than to continue \textbf{SCH}. In this paper we prove that this conjecture is true under some assumption on the uniformity of probability.