並列タイトル等Settling Page Migration Conjecture by Analytical Estimation of Work Functions
タイトル(掲載誌)平成28(2016)年度 科学研究費補助金 基盤研究(C) 研究成果報告書 = 2016 Fiscal Year Final Research Report
一般注記金沢大学理工研究域電子情報通信学系
オンラインアルゴリズムの分野においてよく知られるページ移動問題について研究し,次の通り成果を得た.まず,この問題に対する最良のオンラインアルゴリズムに関する従来の予想を否定する事実を数学的に証明した.次に,ユークリッド空間とリングネットワーク上のオンラインアルゴリズムを設計した.これらのアルゴリズムはいずれも,ページサイズが最小であるという限られた条件の下ではあるが,長年改善が可能かどうか明らかでなかった既存の結果を上回る性能を持つことを明らかにした.
We studied the page migration problem, which is well known in the area of online algorithms, and obtained the following results. First, we mathematically disproved a previous conjecture about an optimal online algorithm for this problem. Then, we designed online algorithms on the Euclidean space and ring networks. We proved that, under the condition that the page size is minimum, both of these algorithms have performance better than previous results that has not been improved for many years.
研究課題/領域番号:26330008, 研究期間(年度):2014-04-01 - 2017-03-31
一次資料へのリンクURLhttps://kanazawa-u.repo.nii.ac.jp/?action=repository_action_common_download&item_id=46316&item_no=1&attribute_id=26&file_no=1
関連情報https://kaken.nii.ac.jp/search/?qm=10282378
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-26330008/
https://kaken.nii.ac.jp/report/KAKENHI-PROJECT-26330008/26330008seika/
連携機関・データベース国立情報学研究所 : 学術機関リポジトリデータベース(IRDB)(機関リポジトリ)