岩間研究室発表論文

2005年度

[ 論文誌 ]

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: 角田大輔, 堀山貴史, 岩間一雄,; ``入札額の範囲が制限された正直なオークション'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.105, COMP2005-6, pp.39--47, 2005年 4月.; >> Abstract

id=2005-02: 山内直哉, 宮崎修一, 岩間一雄,; ``安定結婚問題に対する局所探索近似アルゴリズムの改良'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.105, no.72, COMP2005-15, pp.45--51, 2005年 5月.; >> Abstract

id=2005-05: ※ 小林浩二, 宮崎修一, 岡部寿男,; ``共有メモリ型スイッチにおけるオンラインバッファ管理アルゴリズムの競合比の改良'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.105, no.144, COMP2005-21, pp.17--22, 2005年 6月.; >> Abstract

id=2005-06: 杉原堅也, 伊藤大雄,; ``最大被覆供給点配置問題に関する考察'',; 夏のLAシンポジウム, pp.25.1--25.12, 2005年 7月.; >> Abstract

id=2005-07: 森住大樹, 岩間一雄,; ``否定数を$\log (n+1)$に限定した回路計算量の下界について'',; 夏のLAシンポジウム, pp.30.1--30.4, 2005年 7月.; >> Abstract

id=2005-11: 堀山貴史, 中塚裕之, 岩間一雄,; ``逆算法に基づく詰将棋の列挙'',; 特定領域研究新世代の計算限界ミニ研究集会 (組合せゲーム・パズル), 2005年 9月.; >> Abstract

id=2005-14: T. Horiyama, K. Iwama, and J. Kawahara,; ``Automated Competitive Analysis of Online Problems'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.105, no.344, COMP2005-45, pp.5--12, Oct. 2005.; >> Abstract

id=2005-15: ※ 宮崎修一, 久保浩史, 高見好男, 四方敏明, 櫻井恒正, 山元伸幸, 河野典, 江原康生, 高倉弘喜, 沢田篤史, 中村素典, 岡部寿男, 北野正雄,; ``KUINS接続機器登録データベースの概要'',; 全国共同利用情報基盤センター研究開発論文集, no.27, pp.47--51, 2005年 10月.

id=2005-19: K. Iwama, H. Nishimura, R. Raymond, and S. Yamashita,; ``Transmitting Classical Information on the Quantum Network Efficiently'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.105, no.499, COMP2005-51, pp.15--20, Dec. 2005.; >> Abstract

id=2005-22: 阿武孝文, 堀山貴史, 岩間一雄,; ``二段組合せ回路の最大動作率について'',; 冬のLAシンポジウム, 京都大学数理解析研究所講究録, pp.29.1--29.7, 2006年 1月.; >> Abstract

id=2005-24: M. Hayashi, K. Iwama, H. Nishimura, R. Raymond, and S. Yamashita,; ``Efficient Transmission of the Information on the Quantum Network'',; 冬のLAシンポジウム, 京都大学数理解析研究所講究録, Feb. 2006.

id=2005-26: K. Sugihara, and H. Ito,; ``Maximum-Cover Source-Location Problem with Objective Edge-Connectivity Three'',; 電子情報通信学会回路とシステム研究会, 信学技報, vol.105, no.634, pp.25--29, Mar. 2006.; >> Abstract

id=2005-27: X. Han, K. Iwama, and G. Zhang,; ``Packing Squares with Profits into a Rectangle'',; 電子情報通信学会総合大会講演論文集, ??, pp.??--??, Mar. 2006.

id=2005-29: 高田智史, 伊藤大雄, 中村義作,; ``毒まみれ半順序付き集合ゲームの必勝法'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.105, no.634, pp.13--18, 2006年 3月.; >> Abstract

id=2005-30: K. Iwama, and S. Tamaki,; ``Increasing the Success Probability of PPSZ-type Satisfiability Testing'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.105, no.680, COMP2005-63--68, pp.1--6, Mar. 2006.; >> Abstract

Abstract

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

id=2005-02: 安定結婚問題において，同順位リストと不完全リストの存在を許した問題に対して最大サイズの安定マッチングを見つける問題を考える．この問題はNP困難であり，現在知られている最良の近似アルゴリズムは， $(2-c\frac{\log N}{N})$-近似アルゴリズムである． (ここで，$c$は任意の正定数であり，$N$は入力中の男性の数である．) 本論文では，この近似度を $2-c\frac{1}{N^\frac{2}{3}}$に改良した．($c$は$c \leq \frac{1}{2 \sqrt[3]{6}}$を満たす正定数である．)

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: 供給点配置問題とは，グラフ$G=(V,E)$が与えられたとき，全ての節点を被覆する最小要素の供給点集合$S\subseteq V$を見つける問題である．ただし，節点部分集合$S\subseteq V$が節点$v\in V$を被覆するとは， $S$と$v$の枝連結度が与えられた整数$k$以上となっていることを言う．本稿では，この問題を変形した最大被覆供給点問題を提案し，本問題について考察を行う．本問題は，グラフ$G$と各節点の重みが与えられたとき，被覆される節点の重みの和が最大となるような要素数が$p$個の供給点集合$S\subseteq V$をみつける問題である．本稿では，$k=2$の場合における$O(np+n\log n+m)$時間アルゴリズムを示し，特に$G$が連結グラフの場合には線形時間アルゴリズムが存在することを示す．このアルゴリズムは，与えられた節点重みの付いた木から葉が$p$個の最大重み部分木をみつけるというサブルーチンを用いており，このサブルーチンはダイクストラによる木の最長路を求めるアルゴリズムの拡張となっている．さらに本稿では，$G$が$(k-1)$-枝連結グラフの場合や木の場合における多項式時間アルゴリズムを示す．また，$G$が有向グラフの場合，もしくは節点に供給点を配置するコストを与えた場合に本問題がNP-困難となることを示す．

id=2005-07: 本稿では，否定数を$\log(n+1)$に限定した回路における $n$入力2出力論理関数(PARITY, $\neg$PARITY)の回路計算量の下界が$5n-c$であることを示す．否定数を限定しない場合の現在知られている最高の下界は $5n-o(n)$であるが，否定数を限定することによってそれより上の下界が得られることも期待できる．本稿の内容は，$5n-o(n)$を越えることには至っていないが，より単純な関数を用いてほぼ同等の下界を得るものである．また，否定数を$\lceil \log(n+1) \rceil$に限定した回路において $\omega(n\log(n))$の下界を示すことができれば，一般の回路における同等の下界を示したことになることが知られており，否定数を$\lceil \log(n+1) \rceil$に限定した回路の回路計算量を調べることは特別な意味を持つ．

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: 近年の計算機の高速化やメモリ量の増加、洗練されたアルゴリズム設計法の発展により、与えられた条件を満たす解を1つだけでなくすべて列挙することが、実用上要請されるようになってきている。本発表では、逆算法による詰将棋の列挙アルゴリズムを提案する。逆算法により詰め手数の少ないものから順に詰将棋を列挙することで、詰将棋解答プログラムを用いることなく、与えられた条件下で可能な詰将棋を高速に列挙することができる。

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: 回路の消費電力は回路が消費する平均電力と最大電力の二つの観点から問題視される．本稿では後者の最大電力に注目し， 2入力のANDゲートとNOTゲートから構成される一般の$n$入力の二段組合せ回路について，ゲート出力が変化したときのみ電力消費が発生するとして単純にモデル化を行った．更に入力変化に対応する消費電力の指標として回路の動作率を定義し，回路入力$n > 4$の場合について回路ごとに異なる最大動作率の下限を $n$の関数の形で示した．また$n = 4$の場合には下限を実現する回路を提示し下限がタイトであることを示した．

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: 組み合わせゲームの1つに，Poset (半順序付き集合) Game と呼ばれるものがある．Poset Game は有名な Nim から未解決の Chomp まで多様なゲームを含み，この研究から様々な面白い結果が得られている． Poset Game は単一の祖先 (毒節点) を持つ dag で表現できる．これの拡張として，毒節点が複数あり，しかも毒に重みを持たせ，与えられた体力を越えて毒を取った競技者が負けるというゲームが考えられる．我々はこのゲームの多項式時間で必勝手順を得る方法について考察する．

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.

岩間研究室 発表論文

2005年度

[ 論文誌 ]

[ 国際会議 ]

[ 国内発表 ]

Abstract

岩間研究室発表論文