文献

J-GLOBAL ID：202002218051430512   整理番号：20A0425690

ビンパッキング問題のための並列オンラインアルゴリズム【JST・京大機械翻訳】

Parallel Online Algorithms for the Bin Packing Problem

著者 (4件)： Fekete Sandor P. (Department of Computer Science, TU Braunschweig, Braunschweig, Germany) ,  Grosse-Holz Jonas (Department of Computer Science, TU Braunschweig, Braunschweig, Germany) ,  Keldenich Phillip (Department of Computer Science, TU Braunschweig, Braunschweig, Germany) ,  Schmidt Arne (Department of Computer Science, TU Braunschweig, Braunschweig, Germany)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 11926  ページ： 106-119  発行年： 2020年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 並列オンラインアルゴリズムを研究した。いくつかの固定整数kに対して,同じ系列のイベントに関するオンライン決定を実行するk並列プロセスの集団は,kコピーアルゴリズムを形成する。任意の与えられた時間と入力シーケンスに対して,全体の性能はkの個々の全結果の最良によって決定される。このタイプの問題を,オンライン実行時間最小化のために考慮した。それらはまた,将来のイベント,すなわち,前もって利用可能な多くのビットに関するアドバイスによる最適化にも関連している。筆者らは,オンラインBin Packing問題に対するkコピーアルゴリズムの比較的単純なファミリーである予測調和[数式:原文を参照](PH3)を開発し,その結合競合係数はkを増加させるために1.5に収束する。特に,[数式:原文を参照]は,PH3に対して1.5714の因子を保証することを示し,それは1.57829より良く,最良の既知の1コピーアルゴリズムの性能,[数式:原文を参照]は1.5406の因子を達成し,単一のオンラインアルゴリズムに対して1.54278の既知下限を得た。アドバイスによるオンライン最適化の文脈において,著者らのアプローチは,4ビットが,154278のこの限界より良い因子を達成することを意味した。それは15ビットの以前の限界よりかなり少なかった。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： ビンパッキング問題 ,  *並列処理 ,  最適化
準シソーラス用語： 実行時間 ,  *オンライン ,  *オンラインアルゴリズム , 【Automatic Indexing@JST】

著者キーワード (3件)： オンラインアルゴリズム ,  ビンパッキング ,  競合分析

分類 (2件)： 分子・遺伝情報処理  (JE15040B) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (2件)： ビンパッキング問題 ,  オンラインアルゴリズム