文献

J-GLOBAL ID：202202224574734560   整理番号：22A1045775

下限と部分集合和による下界のスケジューリング【JST・京大機械翻訳】

Scheduling lower bounds via AND subset sum

著者 (4件)： Abboud Amir (IBM Almaden Research Center, San Jose, CA, USA) ,  Bringmann Karl (Saarland University and Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbruecken, Germany) ,  Hermelin Danny (Ben-Gurion University of the Negev, Marcus Family Campus, Beer Sheva, Israel) ,  Shabtay Dvir (Ben-Gurion University of the Negev, Marcus Family Campus, Beer Sheva, Israel)
資料名： Journal of Computer and System Sciences  (Journal of Computer and System Sciences)
巻： 127  ページ： 29-40  発行年： 2022年 
JST資料番号： B0861A  ISSN： 0022-0000  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： Subset SumのNインスタンス(X1,t1),...,(XN,tN)を与えられた場合,ANDサブセットSum問題は,これらのインスタンスの全てがyes-インスタンスであるかどうかを決定する。すなわち,整数Xiの各セットが,目標整数tiまで合計する部分集合を持つかどうかである。この問題は,t_max=maxi_tiおよび任意のΔ|_0に対して,時間O((Nt_max)_1-ε)で解くことができず,∀∃強指数時間仮説(ΔΣ-SETH)を仮定した。次に,この結果を用いて,ΔΣ-SETHを仮定して,最大処理時間p_maxを有するnジョブに関するいくつかのスケジューリング問題に対するO(n+pmaxn1-ε)-時間アルゴリズムを除外した。これらは,1||ΣwjUjのような古典的問題,単一マシン上のタールdyジョブの全重みを最小化する問題,およびP2||ΣUj,2つの同一並列マシン上の遅延ジョブの数を最小化する問題を含む。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  時間 ,  加工時間 ,  *スケジューリング ,  タール ,  問題 ,  整数 ,  *部分集合 ,  並列計算機
準シソーラス用語： *下界 , 【Automatic Indexing@JST】

著者キーワード (6件)： スケジューリング ,  単一機械問題 ,  並列マシン問題 ,  SETH ,  部分集合和 ,  下界

分類 (2件)： グラフ理論基礎  (IA02020S) ,  オペレーティングシステム  (JD03020J)

タイトルに関連する用語 (4件)： 下限 ,  部分集合 ,  下界 ,  スケジューリング