文献

J-GLOBAL ID：201902219998139530   整理番号：19A1660652

オンラインビン被覆型問題の下界【JST・京大機械翻訳】

Lower bounds for online bin covering-type problems

著者 (3件)： Balogh Janos (Department of Applied Informatics, Gyula Juhasz Faculty of Education, University of Szeged, Szeged, Hungary) ,  Epstein Leah (Department of Mathematics, University of Haifa, Haifa, Israel) ,  Levin Asaf (Faculty of Industrial Engineering and Management, The Technion, Haifa, Israel)
資料名： Journal of Scheduling  (Journal of Scheduling)
巻： 22  号： 4  ページ： 487-497  発行年： 2019年 
JST資料番号： W1714A  ISSN： 1094-6136  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 著者らは,これらの問題に対するオンラインアルゴリズムの漸近的競合比に関する,ビン被覆のいくつかの変種を研究し,下限を設計した。著者らの主な結果は,著者らの新しい下限が[数式:原文を参照]であり,以前に知られている[数式:原文を参照]の下限を改善し,Alonらにより20年以上前に証明された,[数式:原文を参照]次元をカバーするベクトルに対するものである。ベクトル被覆の2つの特別な事例も考慮した。著者らは,基数制約問題によるビン被覆の漸近的競合比に対して,約2.8228の改善された下限を証明し,また,小さい成分をもつベクトル被覆を研究し,それに対してdのタイトな限界を示した。最後に,一次元ブラックとホワイトカバーのための三つのモデルを定義し,有限漸近競合比のオンラインアルゴリズムがそれらのために設計できないことを示した。Copyright 2018 Springer Science+Business Media, LLC, part of Springer Nature Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 一次元 ,  *被覆 ,  ベクトル
準シソーラス用語： 基数 ,  競合比 ,  オンラインアルゴリズム ,  *下界 , 【Automatic Indexing@JST】

著者キーワード (3件)： 競合分析 ,  下界 ,  ビンカバー

分類 (2件)： ネットワーク法  (KA03040X) ,  工程管理  (KB03030P)

タイトルに関連する用語 (4件)： オンライン ,  ビン ,  問題 ,  下界