Non-clairvoyant Scheduling with Partial Predictions - Ensai, Ecole Nationale de la Statistique et de l'Analyse de l'Information
Conference Papers Year : 2024

Non-clairvoyant Scheduling with Partial Predictions

Abstract

The non-clairvoyant scheduling problem has gained new interest within learning-augmented algorithms, where the decision-maker is equipped with predictions without any quality guarantees. In practical settings, access to predictions may be reduced to specific instances, due to cost or data limitations. Our investigation focuses on scenarios where predictions for only $B$ job sizes out of $n$ are available to the algorithm. We first establish near-optimal lower bounds and algorithms in the case of perfect predictions. Subsequently, we present a learning-augmented algorithm satisfying the robustness, consistency, and smoothness criteria, and revealing a novel tradeoff between consistency and smoothness inherent in the scenario with a restricted number of predictions.
Fichier principal
Vignette du fichier
1275_Non_clairvoyant_Schedulin.pdf (676.5 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-04709576 , version 1 (25-09-2024)

Identifiers

Cite

Ziyad Benomar, Vianney Perchet. Non-clairvoyant Scheduling with Partial Predictions. ICML 2024 - The 41st International Conference on Machine Learning, Jul 2024, Vienna, Austria. ⟨hal-04709576⟩
41 View
15 Download

Altmetric

Share

More