論文の概要: Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints

• arxiv url: http://arxiv.org/abs/2301.12863v1
• Date: Mon, 30 Jan 2023 13:17:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-31 14:51:56.672489
• Title: Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints
• Title（参考訳）: オンライン優先制約によるジョブスケジュールの最小化
• Authors: Alexandra Lassota, Alexander Lindermayr, Nicole Megow, Jens Schl\"oter
• Abstract要約: オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
• 参考スコア（独自算出の注目度）: 117.8317521974783
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider non-clairvoyant scheduling with online precedence constraints, where an algorithm is oblivious to any job dependencies and learns about a job only if all of its predecessors have been completed. Given strong impossibility results in classical competitive analysis, we investigate the problem in a learning-augmented setting, where an algorithm has access to predictions without any quality guarantee. We discuss different prediction models: novel problem-specific models as well as general ones, which have been proposed in previous works. We present lower bounds and algorithmic upper bounds for different precedence topologies, and thereby give a structured overview on which and how additional (possibly erroneous) information helps for designing better algorithms. Along the way, we also improve bounds on traditional competitive ratios for existing algorithms.
• Abstract（参考訳）: 我々は、オンラインの優先順位制約付き非透視型スケジューリングを考える。アルゴリズムはいかなる仕事にも依存せず、前任者がすべて完了した場合にのみジョブについて学習する。 古典的競合分析における強い不合理性を考慮し,アルゴリズムが品質保証なしに予測にアクセスできる学習強化環境での問題点を考察する。 従来提案されてきた新しい問題固有モデルと一般モデルという,さまざまな予測モデルについて論じる。 我々は,先行トポロジーの下位境界とアルゴリズム上界を提示することにより,アルゴリズムの設計にどの情報を追加するか,どのように役立つか,構造的な概要を示す。 その過程で、既存のアルゴリズムの従来の競争比率の境界も改善します。

関連論文リスト

• Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms [6.131022957085439]
  本稿では,ユーザ特定プロファイルを用いて,アルゴリズムの性能のスムーズさを強制する新しいフレームワークを提案する。 我々は、この新しいアプローチを、よく研究されたオンライン問題、すなわち片道取引問題に適用する。
  論文  参考訳（メタデータ） (2024-08-07T23:15:21Z)
• 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)
• 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)
• Metalearning Linear Bandits by Prior Update [7.519872646378836]
  完全なベイズ的アプローチは、問題のパラメータは既知の事前から生成されると仮定するが、実際にはそのような情報は欠落することが多い。 この問題は、ある部分的な情報を持つ意思決定設定において悪化し、不特定事前の使用は、探索の質が悪く、性能が劣る可能性がある。 この研究において、線形帯域幅とガウス事前の文脈において、事前推定が真の事前に十分近い限り、不特定事前を用いたアルゴリズムの性能は真の先行を用いたアルゴリズムのそれに近いことを証明した。
  論文  参考訳（メタデータ） (2021-07-12T11:17:01Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
  論文  参考訳（メタデータ） (2020-10-22T04:51:01Z)

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

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