| 講演名 | 2014-03-10 直径計算の分散近似に対する時間複雑さ 泉 泰介 /, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では,重み付きネットワークにおける,全点対最短経路の長さの(1+ε)-近似を計算する新しい分散アルゴリズムを提案する.このアルゴリズムはCONGESTモデルで動作し,任意に小さな定数ε>0に対してO^^-(n)時間で停止することが保証されている.距離スケッチ等を用いる既存の方法等と比較して,我々の結果は既存の近似率上界を大幅に改善している.本稿ではまた,CONGESTモデル上において,任意の小さな定数εに対し,重み付きネットワークの直径の(2-ε)-近似値を求める問題を解くo(n/log n)時間のアルゴリズムが存在しないことを示す。この結果は我々の結果が近似率および計算時間の両方においてほぼ最適であることを意味している.この上界および下界の結果は,近似率2の周辺で問題の困難性が大きく変化することを意昧している.これは重みなしネットワークにおける同問題が近似率3/2周辺で困難性が大きく変わることとの対比という点で興味深い現象である. |
| 抄録(英) | We propose a new distributed algorithm for approximated all-pairs weighted distances in the so-called CONGEST model. Our algorithm achieves an approximation factor of (1 + ε) for an arbitrary small constant E and terminates in O^^-(n) rounds. This is the first result explicitly considering all-pairs distance computation in weighted networks. Compared with the previous work implicitly considering this problem (e.g., algorithms for distance sketches), our result substantially improves the approximation bound. We also show that for anyε< 1 there is no algorithm computing a (2 -ε)-approximation of the diameter within o(n/ log n) rounds. This result implies that our algorithm is near-optimal in terms of both time and approximation factor. In other words, the combination of these two results exhibit a threshold of the hardness around approximation factor 2, which is interesting in comparison with the unweighted case that exhibits a phase change around factor 3/2. |
| キーワード(和) | 完全マッチング計数問題 / 指数時間アルゴリズム / 符号理論 / マックウィリアムスの恒等式 |
| キーワード(英) | counting perfect matchings / exponential algorithm / coding theory / MacWilliams Identity |
| 資料番号 | COMP2013-69 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2014/3/3(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 直径計算の分散近似に対する時間複雑さ |
| サブタイトル（和） | |
| タイトル（英） | On Complexity of Distributed Diameter Approximation |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 完全マッチング計数問題 / counting perfect matchings |
| キーワード(2)（和/英） | 指数時間アルゴリズム / exponential algorithm |
| キーワード(3)（和/英） | 符号理論 / coding theory |
| キーワード(4)（和/英） | マックウィリアムスの恒等式 / MacWilliams Identity |
| 第 1 著者 氏名（和/英） | 泉 泰介 / / Taisuke IZUMI |
| 第 1 著者 所属（和/英） | 名古屋工業大学 / Nagoya Institute of Technology |
| 発表年月日 | 2014-03-10 |
| 資料番号 | COMP2013-69 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | 488 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |