arXiv:2511.16194cs.LG2025-11AAAI被引 1

提出可自适应切换的在线区间调度框架,兼顾预测精度与鲁棒性。

A Switching Framework for Online Interval Scheduling with Predictions

  • 设计半信任切换框架,动态融合预测算法与经典调度策略。
  • 在预测准确时性能接近最优,在错误时仍保持稳健表现。
  • 适用于多种算法类型,适合需要稳定性的实时调度场景。

研究不可撤销的在线区间调度问题,要求每个区间到达时立即决定接受或拒绝,目标是最大化被接受区间的总长度,且不发生重叠。考虑学习增强设置下,算法可访问机器学习预测。目标是设计能利用预测提升性能,同时在预测出错时仍具备鲁棒保证的算法。本文提出半信任-切换(SemiTrust-and-Switch)框架,统一结合基于预测与经典区间调度算法。该框架适用于确定性和随机性算法,并刻画了一致性(预测准确时性能)与鲁棒性(对抗输入下性能)之间的权衡。此外,我们给出下界,证明该框架在特定情形下的紧致性。进一步设计了一种随机算法,能平滑介于预测导向与鲁棒算法之间,其性能随预测质量下降而渐进劣化。

原文摘要 · Abstract (English)

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.

在线调度预测增强算法鲁棒性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。