WEKO3
インデックスリンク
アイテム
{"_buckets": {"deposit": "478fe708-a0c7-44d9-93ab-552835b47b49"}, "_deposit": {"created_by": 18, "id": "43325", "owners": [18], "pid": {"revision_id": 0, "type": "depid", "value": "43325"}, "status": "published"}, "_oai": {"id": "oai:kanazawa-u.repo.nii.ac.jp:00043325", "sets": ["936"]}, "author_link": ["73439", "70003", "70004"], "item_4_biblio_info_8": {"attribute_name": "書誌情報", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2016-08-23", "bibliographicIssueDateType": "Issued"}, "bibliographicIssueNumber": "3", "bibliographicPageStart": "57", "bibliographicVolumeNumber": "9", "bibliographic_titles": [{"bibliographic_title": "Algorithms"}]}]}, "item_4_creator_33": {"attribute_name": "著者別表示", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "松林, 昭"}], "nameIdentifiers": [{"nameIdentifier": "70004", "nameIdentifierScheme": "WEKO"}]}]}, "item_4_description_21": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "The page migration problem in Euclidean space is revisited. In this problem, online requests occur at any location to access a single page located at a server. Every request must be served, and the server has the choice to migrate from its current location to a new location in space. Each service costs the Euclidean distance between the server and request. A migration costs the distance between the former and the new server location, multiplied by the page size. We study the problem in the uniform model, in which the page has size D = 1. All request locations are not known in advance; however, they are sequentially presented in an online fashion. We design a 2.75-competitive online algorithm that improves the current best upper bound for the problem with the unit page size. We also provide a lower bound of 2.732 for our algorithm. It was already known that 2.5 is a lower bound for this problem. © 2016 by the authors; licensee MDPI, Basel, Switzerland.", "subitem_description_type": "Abstract"}]}, "item_4_description_5": {"attribute_name": "提供者所属", "attribute_value_mlt": [{"subitem_description": "金沢大学理工研究域電子情報学系 ", "subitem_description_type": "Other"}]}, "item_4_identifier_registration": {"attribute_name": "ID登録", "attribute_value_mlt": [{"subitem_identifier_reg_text": "10.24517/00049671", "subitem_identifier_reg_type": "JaLC"}]}, "item_4_publisher_17": {"attribute_name": "出版者", "attribute_value_mlt": [{"subitem_publisher": "MDPI AG"}]}, "item_4_relation_12": {"attribute_name": "DOI", "attribute_value_mlt": [{"subitem_relation_type": "isIdenticalTo", "subitem_relation_type_id": {"subitem_relation_type_id_text": "10.3390/a9030057", "subitem_relation_type_select": "DOI"}}]}, "item_4_rights_23": {"attribute_name": "権利", "attribute_value_mlt": [{"subitem_rights": "Copyright © 2016 by the authors; licensee MDPI, Basel, Switzerland."}]}, "item_4_source_id_9": {"attribute_name": "ISSN", "attribute_value_mlt": [{"subitem_source_identifier": "1999-4893", "subitem_source_identifier_type": "ISSN"}]}, "item_4_version_type_25": {"attribute_name": "著者版フラグ", "attribute_value_mlt": [{"subitem_version_resource": "http://purl.org/coar/version/c_970fb48d4fbd8a85", "subitem_version_type": "VoR"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "Khorramian, Amanj"}], "nameIdentifiers": [{"nameIdentifier": "73439", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Matsubayashi, Akira"}], "nameIdentifiers": [{"nameIdentifier": "70003", "nameIdentifierScheme": "WEKO"}, {"nameIdentifier": "10282378", "nameIdentifierScheme": "e-Rad", "nameIdentifierURI": "https://kaken.nii.ac.jp/ja/search/?qm=10282378"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2018-01-05"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "TE-PR-MATSUBAYASHI-A-57.pdf", "filesize": [{"value": "628.3 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_6", "mimetype": "application/pdf", "size": 628300.0, "url": {"label": "TE-PR-MATSUBAYASHI-A-57.pdf", "url": "https://kanazawa-u.repo.nii.ac.jp/record/43325/files/TE-PR-MATSUBAYASHI-A-57.pdf"}, "version_id": "43755c05-be24-4b10-ba03-b2ad99b31d81"}]}, "item_keyword": {"attribute_name": "キーワード", "attribute_value_mlt": [{"subitem_subject": "Adversary model", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Competitive analysis", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Euclidean space", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Online algorithms", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Page migration problem", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Server problems", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Uniform model", "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": "Uniform page migration problem in Euclidean space", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "Uniform page migration problem in Euclidean space"}]}, "item_type_id": "4", "owner": "18", "path": ["936"], "permalink_uri": "https://doi.org/10.24517/00049671", "pubdate": {"attribute_name": "公開日", "attribute_value": "2018-01-05"}, "publish_date": "2018-01-05", "publish_status": "0", "recid": "43325", "relation": {}, "relation_version_is_last": true, "title": ["Uniform page migration problem in Euclidean space"], "weko_shared_id": -1}
Uniform page migration problem in Euclidean space
https://doi.org/10.24517/00049671
https://doi.org/10.24517/00049671cfb8d534-1b70-4d3d-9b62-f0e623b06441
名前 / ファイル | ライセンス | アクション |
---|---|---|
TE-PR-MATSUBAYASHI-A-57.pdf (628.3 kB)
|
Item type | 学術雑誌論文 / Journal Article(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2018-01-05 | |||||
タイトル | ||||||
タイトル | Uniform page migration problem in Euclidean space | |||||
言語 | ||||||
言語 | eng | |||||
資源タイプ | ||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
資源タイプ | journal article | |||||
ID登録 | ||||||
ID登録 | 10.24517/00049671 | |||||
ID登録タイプ | JaLC | |||||
著者 |
Khorramian, Amanj
× Khorramian, Amanj× Matsubayashi, Akira |
|||||
著者別表示 |
松林, 昭
× 松林, 昭 |
|||||
提供者所属 | ||||||
内容記述タイプ | Other | |||||
内容記述 | 金沢大学理工研究域電子情報学系 | |||||
書誌情報 |
Algorithms 巻 9, 号 3, p. 57, 発行日 2016-08-23 |
|||||
ISSN | ||||||
収録物識別子タイプ | ISSN | |||||
収録物識別子 | 1999-4893 | |||||
DOI | ||||||
関連タイプ | isIdenticalTo | |||||
識別子タイプ | DOI | |||||
関連識別子 | 10.3390/a9030057 | |||||
出版者 | ||||||
出版者 | MDPI AG | |||||
抄録 | ||||||
内容記述タイプ | Abstract | |||||
内容記述 | The page migration problem in Euclidean space is revisited. In this problem, online requests occur at any location to access a single page located at a server. Every request must be served, and the server has the choice to migrate from its current location to a new location in space. Each service costs the Euclidean distance between the server and request. A migration costs the distance between the former and the new server location, multiplied by the page size. We study the problem in the uniform model, in which the page has size D = 1. All request locations are not known in advance; however, they are sequentially presented in an online fashion. We design a 2.75-competitive online algorithm that improves the current best upper bound for the problem with the unit page size. We also provide a lower bound of 2.732 for our algorithm. It was already known that 2.5 is a lower bound for this problem. © 2016 by the authors; licensee MDPI, Basel, Switzerland. | |||||
権利 | ||||||
権利情報 | Copyright © 2016 by the authors; licensee MDPI, Basel, Switzerland. | |||||
著者版フラグ | ||||||
出版タイプ | VoR | |||||
出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 |