著者

泉 泰介

出版者

一般社団法人 電子情報通信学会

雑誌

電子情報通信学会 基礎・境界ソサイエティ Fundamentals Review (ISSN:18820875)

巻号頁・発行日

vol.10, no.1, pp.46-56, 2016-07-01 (Released:2016-07-02)

参考文献数

19

---

通信複雑性理論とは,複数のプレイヤ間に分散して保持されているデータに対して,何らかの大域的な関数計算を行いたいとき,プレイヤ間で交換しなければならないビット数の上下界を明らかにする理論である.本解説では,同理論の基礎について概説するとともに,強力かつ新たなアプローチとして近年注目を集める,情報理論的手法を用いた通信複雑性の限界解明手法について,その基本的なアイデアを紹介する.

著者

泉 朋子 泉 泰介 小野 廣隆 和田 幸一

出版者

一般社団法人情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2009, no.18, pp.49-56, 2009-02-26

---

証明書分散問題(Minimum Certificate Dispersal Problem, MCD)とは,グラフGと要求集合Rが与えられたときに,Rに含まれるすべての要求を満たすよう各ノードにGの辺を割り当て,各ノードに割り当てられる辺の総数を最小化する問題である.要求とはグラフG上の異なる2つのノードの順序対で表され,要求(u, v)を満たすにはノードu, vに割り当てる辺の和集合にGにおけるuからvへの経路が含まれる必要がある.MCDは与えられるグラフが強連結の場合においてもNP-困難であることが既に示されている.本研究では,MCDの近似可能性について議論する.まず,強連結グラフにおいてMCDの近似率の下界がOmega(log n)(nはGのノード数)であることを示し,さらに任意のグラフにおけるMCDに対する多項式時間O(log n)-近似アルゴリズムが構成可能であることを示す.また,既存研究において多項式時間2-近似アルゴリズムであると評価されていたアルゴリズムが,無向グラフを入力とするMCDに対しては多項式時間3/2-近似アルゴリズムであることを示す.Assume that G is a graph and that R is a set of requests which is represented by a reachable ordered pair of nodes in G. The problem discussed in this paper requires us to assign edges to each node such that all requests in R are satisfied and the total number of edges all nodes have is minimized for a given G and R. To satisfy a request (u, v), a set of assigned edges to u and v must contain a path from u to v in G. This problem is called the Minimum Certificate Dispersal problem (MCD) and is NP-hard even if the input graph is restricted to a strongly connected one. In this paper, we consider approximability of MCD. We clarify an optimal approximability / inapproximability bound in terms of order: we prove the approximation ratio of MCD for strongly connected graphs is Omega (log n) and MCD has a polynomial time approximation algorithm whose factor is O(log n) (n is the number of nodes in G). In addition, we prove that when a given graph is restricted to an undirected graph, the MCD algorithm proposed in [11] guarantees 3/2 approximation ratio.