論文の概要: A Switching Framework for Online Interval Scheduling with Predictions

• arxiv url: http://arxiv.org/abs/2511.16194v1
• Date: Thu, 20 Nov 2025 10:01:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-21 17:08:52.560545
• Title: A Switching Framework for Online Interval Scheduling with Predictions
• Title（参考訳）: 予測付きオンライン間隔スケジューリングのための切り替えフレームワーク
• Authors: Antonios Antoniadis, Ali Shahheidar, Golnoosh Shahkarami, Abolfazl Soltani,
• Abstract要約: 我々は、各区間を即時に受け入れるか、到着時に拒否しなければならない、取り消し不能な環境でのオンライン区間スケジューリングについて検討する。 我々は,この問題を,アルゴリズムが(機械学習による)予測にアクセスできる学習拡張環境で考える。 私たちの主な貢献はSemiTrust-and-Switchフレームワークであり、予測ベースと古典的間隔スケジューリングアルゴリズムを組み合わせた統一的なアプローチを提供する。
• 参考スコア（独自算出の注目度）: 4.352962539265558
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study online interval scheduling in the irrevocable setting, where each interval must be immediately accepted or rejected upon arrival. The objective is to maximize the total length of accepted intervals while ensuring that no two accepted intervals overlap. We consider this problem in a learning-augmented setting, where the algorithm has access to (machine-learned) predictions. The goal is to design algorithms that leverage these predictions to improve performance while maintaining robust guarantees in the presence of prediction errors. Our main contribution is the SemiTrust-and-Switch framework, which provides a unified approach for combining prediction-based and classical interval scheduling algorithms. This framework applies to both deterministic and randomized algorithms and captures the trade-off between consistency (performance under accurate predictions) and robustness (performance under adversarial inputs). Moreover, we provide lower bounds, proving the tightness of this framework in particular settings. We further design a randomized algorithm that smoothly interpolates between prediction-based and robust algorithms. This algorithm achieves both robustness and smoothness--its performance degrades gracefully with the quality of the prediction.
• Abstract（参考訳）: 我々は、各区間を即時に受け入れるか、到着時に拒否しなければならない、取り消し不能な環境でのオンライン区間スケジューリングについて検討する。 目的は、許容区間の総延長を最大化し、2つの許容区間が重複しないことを保証することである。 我々は,この問題を,アルゴリズムが(機械学習による)予測にアクセスできる学習拡張環境で考える。 目標は、予測エラーの存在下で堅牢な保証を維持しながら、これらの予測を活用してパフォーマンスを向上させるアルゴリズムを設計することである。 私たちの主な貢献はSemiTrust-and-Switchフレームワークであり、予測ベースと古典的間隔スケジューリングアルゴリズムを組み合わせた統一的なアプローチを提供する。 このフレームワークは決定論的アルゴリズムとランダム化アルゴリズムの両方に適用され、一貫性(正確な予測によるパフォーマンス)と堅牢性(逆入力によるパフォーマンス)の間のトレードオフをキャプチャする。 さらに、我々は、特に設定において、このフレームワークの厳密さを証明し、より低いバウンダリを提供します。 さらに、予測に基づくアルゴリズムとロバストなアルゴリズムをスムーズに補間するランダム化アルゴリズムを設計する。 このアルゴリズムは頑健さと滑らかさの両方を実現している。

関連論文リスト

• Relational Conformal Prediction for Correlated Time Series [56.59852921638328]
  時系列における不確実性定量化の問題を相関配列を利用して解決する。 共形予測フレームワークと量子レグレッションに基づく分布自由な新しい手法を提案する。 我々の手法は正確なカバレッジを提供し、関連するベンチマークで最先端の不確実性定量化を実現する。
  論文  参考訳（メタデータ） (2025-02-13T16:12:17Z)
• Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms [6.131022957085439]
  本稿では,ユーザ特定プロファイルを用いて,アルゴリズムの性能のスムーズさを強制する新しいフレームワークを提案する。 我々は、この新しいアプローチを、よく研究されたオンライン問題、すなわち片道取引問題に適用する。
  論文  参考訳（メタデータ） (2024-08-07T23:15:21Z)
• Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions [19.537289123577022]
  有限地平線上の長期制約付きオンライン2段階最適化をT$周期で検討する。 対戦型学習アルゴリズムからオンライン二段階問題のオンラインアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2024-01-02T07:46:33Z)
• Efficient and Differentiable Conformal Prediction with General Function Classes [96.74055810115456]
  本稿では,複数の学習可能なパラメータに対する共形予測の一般化を提案する。 本研究は, クラス内において, ほぼ有効な人口被覆率, ほぼ最適効率を実現していることを示す。 実験の結果,提案アルゴリズムは有効な予測セットを学習し,効率を著しく向上できることがわかった。
  論文  参考訳（メタデータ） (2022-02-22T18:37:23Z)
• 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)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Interpretable Machines: Constructing Valid Prediction Intervals with Random Forests [0.0]
  最近の研究で機械学習アルゴリズムを使用する場合の重要な問題は、解釈能力の欠如です。 Random Forest Regression Learnerのこのギャップへの貢献について紹介します。 いくつかのパラメトリックおよび非パラメトリック予測区間がランダムフォレスト点予測のために提供される。 モンテカルロシミュレーションによる徹底的な調査を行い,提案手法の性能を評価した。
  論文  参考訳（メタデータ） (2021-03-09T23:05:55Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)

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

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