WEKO3
インデックスリンク
アイテム
リングネットワークにおけるファイル配置問題について
http://hdl.handle.net/2297/14257
http://hdl.handle.net/2297/1425770e2291f-eda3-4e97-9477-25eb9ae3cff8
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
TE-PR-MATSUBAYASHI-A-14257.pdf (458.4 kB)
|
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2017-10-03 | |||||
| タイトル | ||||||
| タイトル | リングネットワークにおけるファイル配置問題について | |||||
| タイトル | ||||||
| タイトル | On File Allocation on Uniform Ring Networks | |||||
| 言語 | en | |||||
| 言語 | ||||||
| 言語 | jpn | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
| 資源タイプ | journal article | |||||
| 著者 |
川村, 泰之
× 川村, 泰之× 小林, 正雄× 松林, 昭 |
|||||
| 提供者所属 | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | 金沢大学理工研究域電子情報学系 | |||||
| 書誌情報 |
情報処理学会研究報告. AL, アルゴリズム研究会報告 巻 2007, 号 119, p. 41-47, 発行日 2007-11-30 |
|||||
| ISSN | ||||||
| 収録物識別子タイプ | ISSN | |||||
| 収録物識別子 | 0919-6072 | |||||
| NCID | ||||||
| 収録物識別子タイプ | NCID | |||||
| 収録物識別子 | AN1009593X | |||||
| 出版者 | ||||||
| 出版者 | 情報処理学会 | |||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | ファイル配置問題とは,与えられたネットワーク,データ集合,読み書き要求系列に対し,要求の実現とデータの再配置に必要な通信コストの総和が最小となるように,データを動的に再配置する問題である.本稿では,リングネットワークにおけるファイル配置問題を考える.Bartal,Fiat,Rabaniはあるネットワークでc-競合オンラインシュタイナー木アルゴリズムが存在するとき,そのネットワークにおいて適応オンラインアドバーサリに対する(2+√<3>)c-競合となる確率的アルゴリズムを示した.リングネットワークにおいて2-競合オンラインシュタイナー木アルゴリズムが存在することから,このアルゴリズムはリングネットワークにおいて4+2√<3>(≃7.464)-競合のファイル配置アルゴリズムである.本稿では重みなしリングネットワークにおいて適応オンラインアドバーサリに対する7-競合確率的アルゴリズムを示すとともに,決定的アルゴリズムの競合比の下界4.25を示す. Given a network, a set of data objects, and a sequence of requests, the file allocation problem is to compute dynamic allocation of the data objects on the network so that the total communication cost of services for the requests and allocation of data object is minimized. In this paper we consider the file allocation problem on ring networks. Bartal, Fiat, and Rabani showed that if there exists a c-competitive online Steiner tree algorithm on a network, then there exists a (2+√<3>)c-competitive randomized file allocation algorithm against adaptive-online adversary on the network. Their result implies a 4+2√<3>(≃7,464)-competitive file allocation algorithm against adaptive-online adversary on ring networks since a greedy Steiner tree algorithm is 2-competitive on ring networks. In this paper we show a 7-competitive randomized algorithm against adaptive-online adversary and give a lower bound of 4.25 of deterministic algorithm on uniform ring networks. | |||||
| 権利 | ||||||
| 権利情報 | 利用は著作権の範囲内に限られる | |||||
| 著者版フラグ | ||||||
| 出版タイプ | VoR | |||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||
| 関連URI | ||||||
| 識別子タイプ | URI | |||||
| 関連識別子 | http://www.ipsj.or.jp/ | |||||
| 関連URI | ||||||
| 識別子タイプ | URI | |||||
| 関連識別子 | http://ci.nii.ac.jp/naid/110006533723/ | |||||
