| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2020-03-01 11:30 ［招待講演］Adaptive Algorithm for Finding Connected Dominating Sets in Uncertain Graphs ○Takuro Fukunaga（Chuo Univ.）  COMP2019-48 |
|
| 抄録 | （和） | 与えられた無向グラフの最小重み連結支配集合を求める問題は，無線アドホックネットワークへの応用などから，頻繁に研究されている．本論文では，この問題を確率最適化の枠組みで拡張した問題を考える．この確率最適化問題では，グラフの各頂点は，その頂点が生存しているかどうかを表す状態を持つ．問題の目的は，生存している頂点によって誘導されるグラフの連結支配集合を求めることである．ただし，各頂点の状態はあらかじめ明らかではなく，その確率分布のみが与えられる状況を考える．この問題に対し，本研究では適応的アルゴリズムを考える．適応的アルゴリズムは，ある頂点を選択し，その頂点の周辺の頂点の状態を観測する．このプロセスを，選択した頂点が連結支配集合を構成することが確認できるまで繰り返す．我々の提案アルゴリズムは，選んだ頂点の重み和の期待値が，任意の適応的アルゴリズムによって達成される期待値の高々O(alpha log (1/delta))であることを証明する．ここで，alphaは頂点重みポリマトロイドシュタイナー木問題に対する近似比，deltaは頂点の状態について起こりえるシナリオの発生確率の最小値である． |
| （英） | The problem of finding a minimum-weight connected dominating set (CDS) of a given undirected graph has been studied actively, motivated by operations of wireless ad hoc networks. In this paper, we formulate a new stochastic variant of the problem. In this problem, each node in the graph has a hidden random state, which represents whether the node is active or inactive, and we seek a CDS of the graph that consists of the active nodes. We consider an adaptive algorithm for this problem, which repeat choosing nodes and observing the states of the nodes around the chosen nodes until a CDS is found. Our algorithms have a theoretical performance guarantee that the sum of the weights of the nodes chosen by the algorithm is at most O(alpha log (1/delta)) times that of any adaptive algorithm in expectation, where alph$ is an approximation factor for the node-weighted polymatroid Steiner tree problem and delta is the minimum probability of possible scenarios on the node states. | |
| キーワード | （和） | 連結支配集合 / 適応的最適化 / ポリマトロイドシュタイナー木 / / / / / |
| （英） | connected dominating set / adaptive optimization / polymatroid Steiner tree / / / / / | |
| 文献情報 | 信学技報, vol. 119, no. 433, COMP2019-48, pp. 23-23, 2020年3月. | |
| 資料番号 | COMP2019-48 | |
| 発行日 | 2020-02-23 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2019-48 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2020-03-01 - 2020-03-01 |
| 開催地（和） | 電気通信大学 |
| 開催地（英） | The University of Electro-Communications |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2020-03-COMP |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Adaptive Algorithm for Finding Connected Dominating Sets in Uncertain Graphs |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 連結支配集合 / connected dominating set |
| キーワード(2)（和/英） | 適応的最適化 / adaptive optimization |
| キーワード(3)（和/英） | ポリマトロイドシュタイナー木 / polymatroid Steiner tree |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 福永 拓郎 / Takuro Fukunaga / フクナガ タクロウ |
| 第1著者 所属（和/英） | 中央大学 (略称： 中大) Chuo University (略称： Chuo Univ.) |
| 第2著者 氏名（和/英/ヨミ） | / / |
| 第2著者 所属（和/英） | (略称： ) (略称： ) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2020-03-01 11:30:00 |
| 発表時間 | 60分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2019-48 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | no.433 |
| ページ範囲 | p.23 |
| ページ数 | 1 |
| 発行日 | 2020-02-23 (COMP) |
[研究会発表申込システムのトップページに戻る]