論文の概要: Learning-Augmented Online Scheduling with Parsimonious Preemption

• arxiv url: http://arxiv.org/abs/2605.23255v1
• Date: Fri, 22 May 2026 05:58:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-25 17:29:20.215007
• Title: Learning-Augmented Online Scheduling with Parsimonious Preemption
• Title（参考訳）: 同期プリエンプションによる学習強化オンラインスケジューリング
• Authors: Mugen Blue, Sungjin Im, Alexander Lindermayr,
• Abstract要約: レイテンシを最適化しながらプリエンプションを抑制する学習強化スケジューリングに関する最初の体系的研究を行う。 その結果,1ジョブ当たり$O(1)$プリエンプションのみを精度良く予測する単一および非関連並列マシンに対して$O(1)$-competitiveアルゴリズムが得られた。
• 参考スコア（独自算出の注目度）: 49.18367863905825
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning-augmented algorithms have emerged as a powerful paradigm to surpass traditional worst-case lower bounds by integrating potentially noisy predictions. While this framework has seen success in online scheduling, existing work primarily optimizes job latency while relying on frequent, ``blind'' preemptions. This ignores the fundamental trade-off between algorithmic performance and preemption complexity. We provide the first systematic study of learning-augmented scheduling that curbs preemption while optimizing latency. We establish that the gap between theoretical latency bounds and preemption overhead can be bridged with solid analytical foundations. Our results include $O(1)$-competitive algorithms for single and unrelated parallel machines with only $O(1)$ preemptions per job under accurate predictions, with overhead scaling logarithmically with the prediction error. By providing the first bounded-preemption guarantees for unrelated and malleable machines, we extend the theoretical reach of the learning-augmented framework to more constrained and realistic settings. Finally, our algorithms are validated through experiments.
• Abstract（参考訳）: 学習強化アルゴリズムは、潜在的にノイズの多い予測を統合することで、従来の最悪の下限を超える強力なパラダイムとして現れている。 このフレームワークはオンラインスケジューリングで成功したが、既存の作業は主にジョブのレイテンシを最適化し、頻繁な‘blind’のプリエンプションに依存している。 これはアルゴリズムのパフォーマンスとプリエンプションの複雑さの基本的なトレードオフを無視している。 レイテンシを最適化しながらプリエンプションを抑制する学習強化スケジューリングに関する最初の体系的研究を行う。 理論的な遅延境界とプリエンプションのオーバーヘッドのギャップは、固体解析基盤で埋めることができると証明する。 本研究の結果は,1ジョブ当たり$O(1)$プリエンプションしか持たない単一および非関連並列マシンに対する$O(1)$-competitiveアルゴリズムと,予測誤差と対数的にスケーリングするオーバーヘッドを含む。 非関連で拡張可能なマシンに対して、最初の制限付きプリエンプション保証を提供することにより、学習強化フレームワークの理論的リーチを、より制約付きで現実的な設定にまで拡張する。 最後に、我々のアルゴリズムは実験によって検証される。

関連論文リスト

• A Switching Framework for Online Interval Scheduling with Predictions [4.352962539265558]
  我々は、各区間を即時に受け入れるか、到着時に拒否しなければならない、取り消し不能な環境でのオンライン区間スケジューリングについて検討する。 我々は,この問題を,アルゴリズムが(機械学習による)予測にアクセスできる学習拡張環境で考える。 私たちの主な貢献はSemiTrust-and-Switchフレームワークであり、予測ベースと古典的間隔スケジューリングアルゴリズムを組み合わせた統一的なアプローチを提供する。
  論文  参考訳（メタデータ） (2025-11-20T10:01:09Z)
• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
  論文  参考訳（メタデータ） (2023-01-30T13:17:15Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。 我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。 これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-21T13:18:11Z)
• Learning Predictions for Algorithms with Predictions [49.341241064279714]
  予測器を学習するアルゴリズムに対して,一般的な設計手法を導入する。 オンライン学習の手法を応用して、敵のインスタンスに対して学習し、堅牢性と一貫性のあるトレードオフを調整し、新しい統計的保証を得る。 両部マッチング,ページマイグレーション,スキーレンタル,ジョブスケジューリングの手法を解析することにより,学習アルゴリズムの導出におけるアプローチの有効性を実証する。
  論文  参考訳（メタデータ） (2022-02-18T17:25:43Z)
• Parsimonious Learning-Augmented Caching [29.975391787684966]
  本稿では,学習補助アルゴリズムが同時に予測を利用できるような設定を導入し,研究する。 定量的に類似した結果が得られるが、予測のサブ線形数のみを用いることを示す。
  論文  参考訳（メタデータ） (2022-02-09T03:40:11Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
  論文  参考訳（メタデータ） (2020-10-22T04:51:01Z)

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

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