WEKO3
インデックスリンク
-
RootNode
アイテム
Asymptotically Optimal Online Page Migration on Three Points
http://hdl.handle.net/2297/36497
http://hdl.handle.net/2297/364972cf8d563-53b0-4cd2-a25d-eff757b99140
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
TE-PR-MATSUBAYASHI-A-1035.pdf (226.1 kB)
|
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2017-10-03 | |||||
| タイトル | ||||||
| タイトル | Asymptotically Optimal Online Page Migration on Three Points | |||||
| 言語 | ||||||
| 言語 | eng | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
| 資源タイプ | journal article | |||||
| 著者 |
Matsubayashi, Akira
× Matsubayashi, Akira |
|||||
| 書誌情報 |
Algorithmica 巻 71, 号 4, p. 1035-1064, 発行日 2015-01-01 |
|||||
| ISSN | ||||||
| 収録物識別子タイプ | ISSN | |||||
| 収録物識別子 | 0178-4617 | |||||
| NCID | ||||||
| 収録物識別子タイプ | NCID | |||||
| 収録物識別子 | AA10679010 | |||||
| DOI | ||||||
| 関連タイプ | isVersionOf | |||||
| 識別子タイプ | DOI | |||||
| 関連識別子 | 10.1007/s00453-013-9841-9 | |||||
| 出版者 | ||||||
| 出版者 | Springer Science+Business Media | |||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | This paper addresses the page migration problem: given online requests from nodes on a network for accessing a page stored in a node, output online migrations of the page. Serving a request costs the distance between the request and the page, and migrating the page costs the migration distance multiplied by the page size D≥1. The objective is to minimize the total sum of service costs and migration costs. Black and Sleator conjectured that there exists a 3-competitive deterministic algorithm for every graph. Although the conjecture was disproved for the case D=1, whether or not an asymptotically (with respect to D) 3-competitive deterministic algorithm exists for every graph is still open. In fact, we did not know if there exists a 3-competitive deterministic algorithm for an extreme case of three nodes with D≥2. As the first step toward an asymptotic version of the Black and Sleator conjecture, we present 3- and (3+1/D)-competitive algorithms on three nodes with D=2 and D≥3, respectively, and a lower bound of 3+Ω(1/D) that is greater than 3 for every D≥3. In addition to the results on three nodes, we also derive ρ-competitiveness on complete graphs with edge-weights between 1 and 2-2/ρ for any ρ≥3, extending the previous 3-competitive algorithm on uniform networks. © 2013 Springer Science+Business Media New York. | |||||
| 著者版フラグ | ||||||
| 出版タイプ | AM | |||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||
