論文の概要: Non-Clairvoyant Scheduling with Predictions Revisited
- arxiv url: http://arxiv.org/abs/2202.10199v1
- Date: Mon, 21 Feb 2022 13:18:11 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-23 14:20:38.061677
- Title: Non-Clairvoyant Scheduling with Predictions Revisited
- Title（参考訳）: 予測を再開した非サーベイラントスケジューリング
- Authors: Alexander Lindermayr, Nicole Megow
- Abstract要約: 非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。
我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。
これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
- 参考スコア（独自算出の注目度）: 77.86290991564829
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In non-clairvoyant scheduling, the task is to find an online strategy for
scheduling jobs with a priori unknown processing requirements with the
objective to minimize the total (weighted) completion time. We revisit this
well-studied problem in a recently popular learning-augmented setting that
integrates (untrusted) predictions in online algorithm design. While previous
works used predictions on processing requirements, we propose a new prediction
model, which provides a relative order of jobs which could be seen as
predicting algorithmic actions rather than parts of the unknown input. We show
that these predictions have desired properties, admit a natural error measure
as well as algorithms with strong performance guarantees and that they are
learnable in both, theory and practice. We generalize the algorithmic framework
proposed in the seminal paper by Kumar et al. (NeurIPS'18) and present the
first learning-augmented scheduling results for weighted jobs and unrelated
machines. We demonstrate in empirical experiments the practicability and
superior performance compared to the previously suggested single-machine
algorithms.
- Abstract（参考訳）: 非クレアボイトスケジューリングでは、未処理の未処理条件でジョブをスケジューリングするためのオンライン戦略を見つけ、総(重み付けされた)完了時間を最小化する。
オンラインアルゴリズム設計における予測(信頼できない)を統合した,最近普及した学習型学習環境において,このよく検討された問題を再検討する。
従来の作業では,処理要求に対する予測が用いられていたが,未知の入力の一部ではなく,アルゴリズム的な動作を予測できるような,ジョブの相対的な順序の予測モデルが提案されている。
これらの予測には所望の特性があり、自然な誤差測定と強力な性能保証を持つアルゴリズムを認め、理論と実践の両方で学習可能であることを示す。
Kumarらによるセミナー論文(NeurIPS'18)で提案されたアルゴリズムの枠組みを一般化し、重み付けされたジョブと無関係なマシンに対する最初の学習強化スケジューリング結果を示す。
実験では,従来提案していたシングルマシンアルゴリズムと比較して実用性と優れた性能を示す。
関連論文リスト
- Non-clairvoyant Scheduling with Partial Predictions [17.387787159892287]
本稿では, 頑健性, 一貫性, 滑らかさの基準を満たす学習補助アルゴリズムを提案する。
また,予測数を制限するシナリオに固有の一貫性と滑らかさの新たなトレードオフも提示する。
論文 参考訳（メタデータ） (2024-05-02T05:29:22Z) - Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。
この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。
本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
論文 参考訳（メタデータ） (2024-03-12T08:40:21Z) - Predictive Coding beyond Correlations [59.47245250412873]
このようなアルゴリズムのうちの1つは、予測符号化と呼ばれ、因果推論タスクを実行することができるかを示す。
まず、予測符号化の推論過程における簡単な変化が、因果グラフを再利用したり再定義したりすることなく、介入を計算できることを示す。
論文 参考訳（メタデータ） (2023-06-27T13:57:16Z) - Minimalistic Predictions to Schedule Jobs with Online Precedence
Constraints [117.8317521974783]
オンライン優先制約による非サーボ的スケジューリングについて検討する。
アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
論文 参考訳（メタデータ） (2023-01-30T13:17:15Z) - Algorithms with Prediction Portfolios [23.703372221079306]
我々は、マッチング、ロードバランシング、非クレアボイラントスケジューリングなど、多くの基本的な問題に対する複数の予測器の使用について検討する。
これらの問題のそれぞれに対して、複数の予測器を利用する新しいアルゴリズムを導入し、その結果のパフォーマンスに限界を証明します。
論文 参考訳（メタデータ） (2022-10-22T12:58:07Z) - Learning Predictions for Algorithms with Predictions [49.341241064279714]
予測器を学習するアルゴリズムに対して,一般的な設計手法を導入する。
オンライン学習の手法を応用して、敵のインスタンスに対して学習し、堅牢性と一貫性のあるトレードオフを調整し、新しい統計的保証を得る。
両部マッチング,ページマイグレーション,スキーレンタル,ジョブスケジューリングの手法を解析することにより,学習アルゴリズムの導出におけるアプローチの有効性を実証する。
論文 参考訳（メタデータ） (2022-02-18T17:25:43Z) - Robustification of Online Graph Exploration Methods [59.50307752165016]
我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。
本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-10T10:02:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。