論文の概要: Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary

• arxiv url: http://arxiv.org/abs/2302.00985v2
• Date: Tue, 30 May 2023 11:44:13 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-01 01:37:36.640394
• Title: Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary
• Title（参考訳）: Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not necessary
• Authors: Alexander Lindermayr, Nicole Megow, Martin Rapp
• Abstract要約: 我々は、無関係な(異種な)マシン上でのオンラインスケジューリングを、高速な環境で検討する。 透かしアルゴリズムと非透かしアルゴリズムでは,強い可視性を示す。
• 参考スコア（独自算出の注目度）: 71.46673478666631
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider online scheduling on unrelated (heterogeneous) machines in a speed-oblivious setting, where an algorithm is unaware of the exact job-dependent processing speeds. We show strong impossibility results for clairvoyant and non-clairvoyant algorithms and overcome them in models inspired by practical settings: (i) we provide competitive learning-augmented algorithms, assuming that (possibly erroneous) predictions on the speeds are given, and (ii) we provide competitive algorithms for the speed-ordered model, where a single global order of machines according to their unknown job-dependent speeds is known. We prove strong theoretical guarantees and evaluate our findings on a representative heterogeneous multi-core processor. These seem to be the first empirical results for scheduling algorithms with predictions that are evaluated in a non-synthetic hardware environment.
• Abstract（参考訳）: アルゴリズムがジョブ依存の処理速度を正確に把握していないような,非関連(ヘテロゲネス)マシン上でのオンラインスケジューリングについて検討する。 我々は, 透視的および非透視的アルゴリズムに対する強い不可能性を示し, 実用的設定に触発されたモデルで克服する。 (i)速度の予測が与えられると仮定して、競争力のある学習増強アルゴリズムを提供する。 (ii)我々は、未知のジョブ依存の速度に応じて1つのグローバルオーダーのマシンが知られている速度順序付けモデルのための競合アルゴリズムを提供する。 我々は,その理論的保証を強く証明し,代表的ヘテロジニアスマルチコアプロセッサ上での知見を評価する。 これらは、非合成ハードウェア環境で評価される予測を伴うスケジューリングアルゴリズムの最初の経験的な結果である。

関連論文リスト

• A Stable, Fast, and Fully Automatic Learning Algorithm for Predictive Coding Networks [65.34977803841007]
  予測符号化ネットワークは、ベイズ統計学と神経科学の両方にルーツを持つ神経科学にインスパイアされたモデルである。 シナプス重みに対する更新規則の時間的スケジュールを変更するだけで、元の規則よりもずっと効率的で安定したアルゴリズムが得られることを示す。
  論文  参考訳（メタデータ） (2022-11-16T00:11:04Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。 我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。 これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-21T13:18:11Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• A Fast PC Algorithm with Reversed-order Pruning and A Parallelization Strategy [22.31288740171446]
  PCアルゴリズムは観測データに基づく因果構造発見のための最先端のアルゴリズムである。 条件付き独立テストが実行された場合、最悪の場合、計算コストがかかる可能性がある。 これにより、タスクが数百から数千のノードを含む場合、アルゴリズムは計算的に難解になる。 本稿では、2つのノードを独立にレンダリングする条件セットが非特異であり、特定の冗長ノードを含む場合、結果の精度を犠牲にしない、という批判的な観察を提案する。
  論文  参考訳（メタデータ） (2021-09-10T02:22:10Z)
• Faster Matchings via Learned Duals [31.61057940283721]
  機械学習予測のアイデアと「スタート・ウォーム」原始二元アルゴリズムのアイデアを組み合わせる。 まず、予測可能な双対は実現不可能である可能性があるので、予測できない双対を近くの実現可能な解に効率的にマッピングするアルゴリズムを提供する。 第二に、一度双対が実現可能ならば、それらは最適ではないかもしれない。
  論文  参考訳（メタデータ） (2021-07-20T21:11:09Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。