mlsanityData to 7 Oct 2026

Non-clairvoyant Scheduling with Partial Predictions

arXiv 2405.01013 ↗First posted 2 May 2024cs.LG cs.AI cs.DScited by 7

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 33 of its 62 references that are in the map. First posted on arXiv 2 May 2024.

Builds on

33 of 62 references.

References · 33

  1. 2018Competitive caching with machine learned advicecited by 194
  2. 2017The Case for Learned Index Structurescited by 188
  3. 2020Algorithms with Predictionscited by 152
  4. 2020The Primal-Dual method for Learning Augmented Algorithmscited by 78
  5. 2020Online metric algorithms with untrusted predictionscited by 74
  6. 2020Secretary and Online Matching Problems with Machine Learned Advicecited by 71
  7. 2020Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithmscited by 64
  8. 2021Faster Matchings via Learned Dualscited by 56
  9. 2022Faster Fundamental Graph Algorithms via Learned Predictionscited by 42
  10. 2020Secretaries with Advicecited by 41
  11. 2020Learning Augmented Energy Minimization via Speed Scalingcited by 38
  12. 2022Learning Augmented Binary Search Treescited by 31
21 more
  1. 2021Flow Time Scheduling with Uncertain Processing Timecited by 29
  2. 2022Permutation Predictions for Non-Clairvoyant Schedulingcited by 22
  3. 2017Revenue Optimization with Approximate Bid Predictionscited by 21
  4. 2022Customizing ML Predictions for Online Algorithmscited by 21
  5. 2021Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Boundscited by 20
  6. 2022Parsimonious Learning-Augmented Cachingcited by 19
  7. 2022Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Modelcited by 19
  8. 2022Algorithms with Prediction Portfolioscited by 19
  9. 2021A Novel Prediction Setup for Online Speed-Scalingcited by 17
  10. 2022Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictionscited by 16
  11. 2023Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysiscited by 16
  12. 2023Sorting with Predictionscited by 14
  13. 2021Robust Learning-Augmented Caching: An Experimental Studycited by 12
  14. 2024Algorithms for Caching and MTS with reduced number of predictionscited by 12
  15. 2021Logarithmic Regret from Sublinear Hintscited by 11
  16. 2022Paging with Succinct Predictionscited by 10
  17. 2023Minimalistic Predictions to Schedule Jobs with Online Precedence Constraintscited by 7
  18. 2022On Preemption and Learning in Stochastic Schedulingcited by 6
  19. 2023Metric Clustering and MST with Strong and Weak Distance Oraclescited by 6
  20. 2023Addressing Bias in Online Selection with Limited Budget of Comparisonscited by 3
  21. 2024Accelerating Matroid Optimization through Fast Imprecise Oraclescited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 3; 2026: 2.

7 papers.

  1. 2024Temporal Fair Division of Indivisible Itemscited by 11
  2. 2024Learning-Augmented Priority Queuescited by 7
  3. 2025On Tradeoffs in Learning-Augmented Algorithmscited by 7
  4. 2025Online Fair Division for Personalized 2-Value Instancescited by 3
  5. 2025Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictorscited by 2
  6. 2026Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completioncited by 0
  7. 2026Augmented Hypothesis Testing with Persona-Based LLM Simulationscited by 0