3 点上のオンラインページ移動問題に対する新しい上下界

• Item type: SIG Technical Reports(1)
• 公開日: 2008-10-31
• タイトル: 3 点上のオンラインページ移動問題に対する新しい上下界
• タイトル / 言語: en
• タイトル: New Bounds for Online Page Migration on Three Points
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 金沢大学大学院自然科学研究科電子情報科学専攻
• 著者所属(英): en
• 著者所属(英): Division of Electrical Engineering and Computer Science, Kanazawa University
• 著者名: 松林, 昭
• 著者名(英): Akira, Matsubayashi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ページ移動問題とは，辺重み ω: E→ R+ を持つグラフ G = (V E)，正整数 D，点列 s0 r1 ..... rk ∈ V が与えられ，∑=1 (ds?-1r? + D .ds? - 1s?) を最小化するような点列 s1 ..... sk ∈ V を求める問題である．ただし，duv は u と v を結ぶパスの辺の重みの最小和である．本報告ではこの問題に対する決定的なオンラインアルゴリズムについて考える．すべてのグラフと D に対して 3 より小さい競合比を持つアルゴリズムは存在しないことが知られている．また，3 点上で D = 1 の場合に対する 3-競合アルゴリズムが知られている．しかし，3 点上で D ? 2の場合に対する 3-競合オンラインアルゴリズムが存在するか否かは，著者が知る限り知られていない．本稿では，3 点上で D = 2 の場合には 3-競合アルゴリズムが存在するが，D ? 3 の場合には 3-競合アルゴリズムは存在しないことを示す．また任意の D に対する 3.1467-競合オンラインアルゴリズムを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The page migration problem is as follows: given a graph G = (V,E) with edge weights ω: E→R+, a positive integer D, and nodes s0, r1,...,rk ∈ V, to compute s1,.....,sk V so that the cost function ∑=1 (dsﾎｯ-1rﾎｯ + D.dsﾎｯ-1sﾎｯ) is minimized, where duv is the minimum sum of weights of edges of a path connecting u and v. We consider deterministic online algorithms for the problem. It is known that for any G and D, there exists no online algorithm with a competitive ratio less than 3. It is also known that there exists a 3-competitive algorithm on three points for D = 1. In this report, we prove that there exists a 3-competitive algorithm on three points if D = 2, while there exists no 3-competitive algorithm if D 竕･ 3. We also present a 3.1467-competitive algorithm on three points for any D.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2008, 号 108(2008-AL-120), p. 49-56, 発行日 2008-10-31
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会