WEKO3
インデックスリンク
アイテム
{"_buckets": {"deposit": "a3ca7c2c-9e7a-4fae-a264-5287cd76aad9"}, "_deposit": {"created_by": 3, "id": "8546", "owners": [3], "pid": {"revision_id": 0, "type": "depid", "value": "8546"}, "status": "published"}, "_oai": {"id": "oai:kanazawa-u.repo.nii.ac.jp:00008546", "sets": ["936"]}, "author_link": ["614"], "item_4_biblio_info_8": {"attribute_name": "書誌情報", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2015-01-01", "bibliographicIssueDateType": "Issued"}, "bibliographicIssueNumber": "4", "bibliographicPageEnd": "1064", "bibliographicPageStart": "1035", "bibliographicVolumeNumber": "71", "bibliographic_titles": [{"bibliographic_title": "Algorithmica"}]}]}, "item_4_description_21": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "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.", "subitem_description_type": "Abstract"}]}, "item_4_publisher_17": {"attribute_name": "出版者", "attribute_value_mlt": [{"subitem_publisher": "Springer Science+Business Media"}]}, "item_4_relation_12": {"attribute_name": "DOI", "attribute_value_mlt": [{"subitem_relation_type": "isVersionOf", "subitem_relation_type_id": {"subitem_relation_type_id_text": "10.1007/s00453-013-9841-9", "subitem_relation_type_select": "DOI"}}]}, "item_4_source_id_11": {"attribute_name": "NCID", "attribute_value_mlt": [{"subitem_source_identifier": "AA10679010", "subitem_source_identifier_type": "NCID"}]}, "item_4_source_id_9": {"attribute_name": "ISSN", "attribute_value_mlt": [{"subitem_source_identifier": "0178-4617", "subitem_source_identifier_type": "ISSN"}]}, "item_4_version_type_25": {"attribute_name": "著者版フラグ", "attribute_value_mlt": [{"subitem_version_resource": "http://purl.org/coar/version/c_ab4af688f83e57aa", "subitem_version_type": "AM"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "Matsubayashi, Akira"}], "nameIdentifiers": [{"nameIdentifier": "614", "nameIdentifierScheme": "WEKO"}, {"nameIdentifier": "10282378", "nameIdentifierScheme": "金沢大学研究者情報", "nameIdentifierURI": "http://ridb.kanazawa-u.ac.jp/public/detail.php?kaken=10282378"}, {"nameIdentifier": "10282378", "nameIdentifierScheme": "研究者番号", "nameIdentifierURI": "https://nrid.nii.ac.jp/nrid/1000010282378"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2017-10-03"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "TE-PR-MATSUBAYASHI-A-1035.pdf", "filesize": [{"value": "226.1 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 226100.0, "url": {"label": "TE-PR-MATSUBAYASHI-A-1035.pdf", "url": "https://kanazawa-u.repo.nii.ac.jp/record/8546/files/TE-PR-MATSUBAYASHI-A-1035.pdf"}, "version_id": "ae1ae6e5-8a5c-45be-8618-08c54886b421"}]}, "item_keyword": {"attribute_name": "キーワード", "attribute_value_mlt": [{"subitem_subject": "Competitive analysis", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Page migration", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Server problem", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Work function algorithm", "subitem_subject_scheme": "Other"}]}, "item_language": {"attribute_name": "言語", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"resourcetype": "journal article", "resourceuri": "http://purl.org/coar/resource_type/c_6501"}]}, "item_title": "Asymptotically Optimal Online Page Migration on Three Points", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "Asymptotically Optimal Online Page Migration on Three Points"}]}, "item_type_id": "4", "owner": "3", "path": ["936"], "permalink_uri": "http://hdl.handle.net/2297/36497", "pubdate": {"attribute_name": "公開日", "attribute_value": "2017-10-03"}, "publish_date": "2017-10-03", "publish_status": "0", "recid": "8546", "relation": {}, "relation_version_is_last": true, "title": ["Asymptotically Optimal Online Page Migration on Three Points"], "weko_shared_id": -1}
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 |