文献

J-GLOBAL ID：202002228446622315   整理番号：20A1867602

モバイル施設によるオンライン施設配置【JST・京大機械翻訳】

Online Facility Location with Mobile Facilities

著者 (2件)： Feldkord Bjorn (Paderborn University, Paderborn, Germany) ,  Meyer auf der Heide Friedhelm (Paderborn University, Paderborn, Germany)
資料名： ACM Proceedings  (ACM Proceedings)
号： SPAA ’18  ページ： 373-381  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： オンラインアルゴリズムが位置が変化する距離に比例するコストに対する設備の位置を適応できる拡張版におけるオンライン施設配置問題を調べた。この設定において,オンラインアルゴリズムの構築は,オンライン施設配置の下限インスタンスをはるかに効果的に扱うことができる。Fotakisは,元のオンライン施設配置問題に対して,Omega(l/og log log n)の下限を示し,そこでは,nは数クライアントを示した。この限界は,実際の線上で,また, obiousな敵対者に対するランダム化アルゴリズムに対してさえ成立する。対照的に,本モデルではnに依存しない競合比を達成できる。2つの設定におけるランダム化オンラインアルゴリズムを提案した:著者らはユークリッド空間(任意の次元の)を考察し,各時間ステップで任意の距離mで任意に移動するか,または移動するかのいずれかを許す。施設をbからbに移動させるコストは,D≧1が一定であるD.d(a,b)である。提案アルゴリズムは,メモリレスw.r.t.過去の要求であり,各時間ステップでほとんどの1施設に局所修正を行うだけである。任意の運動の場合,競合比はDのみに依存する。一定の距離mへの移動を制限する場合,競合比はさらに設備とmの開口コストc_fに依存する。その結果,著者らの結果が実際の線上で漸近的に強まることを示した。高次元のユークリッド空間に対して,著者らのアルゴリズムの競合比はD,c_fおよびmに関して緊密であるが,最適設備数によってさらに影響を受ける。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  開口 ,  Euclid空間 ,  高次元 ,  *携帯電話
準シソーラス用語： 敵対者 ,  オンラインアルゴリズム ,  競合比 ,  *オンライン ,  施設配置問題 , 【Automatic Indexing@JST】

著者キーワード (4件)： 競争分析 ,  施設配置 ,  オンラインアルゴリズム ,  資源増大

分類 (2件)： 計算理論  (JB02000A) ,  オペレーティングシステム  (JD03020J)

タイトルに関連する用語 (4件)： モバイル ,  施設 ,  オンライン ,  施設配置