A Switching Framework for Online Interval Scheduling with Predictions
This work addresses the problem of improving scheduling efficiency with predictions for applications like resource allocation, but it is incremental as it builds on existing learning-augmented algorithms.
The paper tackles online interval scheduling with predictions by introducing the SemiTrust-and-Switch framework, which combines prediction-based and classical algorithms to maximize total length of accepted intervals, achieving robustness and smooth performance degradation with prediction errors.
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.