mlsanityData to 7 Oct 2026

Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary

arXiv 2302.00985 ↗First posted 2 Feb 2023cs.DS cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

We consider online scheduling on unrelated (heterogeneous) machines in a speed-oblivious setting, where an algorithm is unaware of the exact job-dependent processing speeds. We show strong impossibility results for clairvoyant and non-clairvoyant algorithms and overcome them in models inspired by practical settings: (i) we provide competitive learning-augmented algorithms, assuming that (possibly erroneous) predictions on the speeds are given, and (ii) we provide competitive algorithms for the speed-ordered model, where a single global order of machines according to their unknown job-dependent speeds is known. We prove strong theoretical guarantees and evaluate our findings on a representative heterogeneous multi-core processor. These seem to be the first empirical results for scheduling algorithms with predictions that are evaluated in a non-synthetic hardware environment.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 17 of its 56 references that are in the map. First posted on arXiv 2 Feb 2023.

Builds on

17 of 56 references.

References · 17

  1. 2020Algorithms with Predictionscited by 152
  2. 2021Flow Time Scheduling with Uncertain Processing Timecited by 29
  3. 2022Permutation Predictions for Non-Clairvoyant Schedulingcited by 22
  4. 2022Algorithms with Prediction Portfolioscited by 19
  5. 2021A Novel Prediction Setup for Online Speed-Scalingcited by 17
  6. 2021Distortion-Oblivious Algorithms for Minimizing Flow Timecited by 15
  7. 2022Scheduling with Speed Predictionscited by 6
  8. 2014Competitive Algorithms from Competitive Equilibria: Non-Clairvoyant Scheduling under Polyhedral Constraintscited by 4
  9. 2014SELFISHMIGRATE: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processorscited by 4
  10. 2017An Adversarial Model for Scheduling with Testingcited by 4
  11. 2017Greed Works -- Online Algorithms For Unrelated Machine Stochastic Schedulingcited by 3
  12. 2020Speed-Robust Scheduling -- Sand, Bricks, and Rockscited by 3
5 more
  1. 2021Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Timescited by 3
  2. 2015Lift-and-Round to Improve Weighted Completion Time on Unrelated Machinescited by 2
  3. 2020Explorable Uncertainty in Scheduling with Non-Uniform Testing Timescited by 2
  4. 2022Improved Approximations for Unrelated Machine Schedulingcited by 2
  5. 2017Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxationscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 2; 2025: 0; 2026: 2.

5 papers.

  1. 2023Out-of-Distribution-Aware Electric Vehicle Chargingcited by 1
  2. 2024Energy-Efficient Scheduling with Predictionscited by 1
  3. 2024A Data-Driven Approach to Dataflow-Aware Online Scheduling for Graph Neural Network Inferencecited by 0
  4. 2026Learning-Augmented Online Scheduling with Parsimonious Preemptioncited by 0
  5. 2026Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implicationscited by 0