WEKO3
インデックスリンク
アイテム
リングネットワークにおけるページ移動について
http://hdl.handle.net/2297/14258
http://hdl.handle.net/2297/142586382300a-0796-4f38-8319-828505062107
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
TE-PR-TATSUBAYASHI-A-35.pdf (740.7 kB)
|
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2017-10-03 | |||||
| タイトル | ||||||
| タイトル | リングネットワークにおけるページ移動について | |||||
| タイトル | ||||||
| タイトル | Page Migration on Ring Networks | |||||
| 言語 | en | |||||
| 言語 | ||||||
| 言語 | jpn | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
| 資源タイプ | journal article | |||||
| 著者 |
松林, 昭
× 松林, 昭 |
|||||
| 提供者所属 | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | 金沢大学理工研究域電子情報学系 | |||||
| 書誌情報 |
情報処理学会研究報告. AL, アルゴリズム研究会報告 巻 2006, 号 122, p. 35-42, 発行日 2006-11-21 |
|||||
| ISSN | ||||||
| 収録物識別子タイプ | ISSN | |||||
| 収録物識別子 | 0919-6072 | |||||
| NCID | ||||||
| 収録物識別子タイプ | NCID | |||||
| 収録物識別子 | AN1009593X | |||||
| 出版者 | ||||||
| 出版者 | 情報処理学会 | |||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | ページ移動問題とは,ネットワーク上でページと呼ばれるデータへのアクセス要求を発行するノード系列に対して,ページを動的に移動することにより要求に対するサービスコストと移動コストの総和を最小化する問題である.この間題に対しては,木,一様ネットワーク,およびそれらのCartesian積を除いて,4未満の競合比を持つ決定的オンラインアルゴリズムは知られていない.本稿では,ページサイズが1に限定されている条件の下で,リングネットワークに対する決定的な2+√<2>(⋍3.4142)-競合オンラインアルゴリズムを示す.このアルゴリズムはリングの木とトーラスにも拡張できる.さらにページ移動問題の競合比の下界として,一般のネットワークに対して3.1639,リングネットワークに対して3.1213を与える. The page migration problem is to compute dynamic allocation of a page on a network for a given sequence of nodes issuing requests for the page. The goal is to minimize the total communication costs of services for requests and of migrations of the page. We did not know any deterministic online algorithm with competitive ratio less than 4 for networks other than trees, uniform networks, and Cartesian products of those networks so far. In this paper we give a 2+√<2>(⋍ 3.4142)-competitive deterministic algorithm on rings (with edge weights) for the setting that the page size is 1. We can also derive algorithms for trees of rings and tori with the same competitive ratio and with the same setting. Moreover, we show an improved lower bound of 3.1639 for general networks and a lower bound of 3.1213 for rings. Our lower bound for rings is the first result which gives an explicit lower bound greater than 3 for rings, together with an explicit proof. | |||||
| 権利 | ||||||
| 権利情報 | 利用は著作権の範囲内に限られる | |||||
| 著者版フラグ | ||||||
| 出版タイプ | VoR | |||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||
| 関連URI | ||||||
| 識別子タイプ | URI | |||||
| 関連識別子 | http://ci.nii.ac.jp/naid/110005717684/ | |||||
| 関連URI | ||||||
| 識別子タイプ | URI | |||||
| 関連識別子 | http://www.ipsj.or.jp/ | |||||
