文献

J-GLOBAL ID：202002238750604712   整理番号：20A0331238

2つの無関係な利己的機械に関する信頼できるスケジューリングのための新しい限界【JST・京大機械翻訳】

New Bounds for Truthful Scheduling on Two Unrelated Selfish Machines

著者 (2件)： Kuryatnikova Olga (Department of Econometrics and Operations Research, Tilburg University, Tilburg, AB, Netherlands) ,  Vera Juan C. (Department of Econometrics and Operations Research, Tilburg University, Tilburg, AB, Netherlands)
資料名： Theory of Computing Systems  (Theory of Computing Systems)
巻： 64  号： 2  ページ： 199-226  発行年： 2020年 
JST資料番号： D0592A  ISSN： 1432-4350  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 著者らは,nタスクと2つの無関係な並列利魚機のための最小メークスパン問題を考察した。R_nをランダム化単調スケールフリーアルゴリズムの最良近似比とした。このクラスは,2つの機械に関する信頼できるスケジューリングのために知られた最も効率的なアルゴリズムを含んでいる。R_nに対する新しいMin-Max定式化と,この定式化に基づくR_n上の上限と下限を提案した。下限に対して,累積分布関数(CDFs)の点状近似を利用した。上界に対して,区分的有理CDFsによる分布を用いてランダム化アルゴリズムを構築した。著者らの方法は,小さなnのためにR_nに関する既存の限界に関して改良した。特に,|R_2-1.505996|<10-6であることを示すn=2に対してほぼ厳密な限界を得た。Copyright The Author(s) 2019 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 定式化 ,  近似法 ,  最適化 ,  *スケジューリング ,  アルゴリズム
準シソーラス用語： 上界 ,  累積分布関数 ,  ランダム化 ,  メイクスパン , 【Automatic Indexing@JST】

著者キーワード (5件)： ミニマックス最適化 ,  信頼できるスケジューリング ,  近似 ,  区分関数 ,  アルゴリズム機構設計

分類 (1件)： システム・制御理論一般  (IA02010H)

タイトルに関連する用語 (3件)： 信頼 ,  スケジューリング ,  限界