mlsanityData to 7 Oct 2026

Improving Online Algorithms via ML Predictions

arXiv 2407.17712 ↗First posted 25 Jul 2024cs.DS cs.LGcited by 65

Not on the map. Why?

Abstract (arXiv)

In this work we study the problem of using machine-learned predictions to improve the performance of online algorithms. We consider two classical problems, ski rental and non-clairvoyant job scheduling, and obtain new online algorithms that use predictions to make their decisions. These algorithms are oblivious to the performance of the predictor, improve with better predictions, but do not degrade much if the predictions are poor.

Key facts. Cited by 65 papers in the map (data through 7 Oct 2026). Builds on 5 of its 24 references that are in the map. First posted on arXiv 25 Jul 2024.

Builds on

5 of 24 references.

References · 5

  1. 2018Competitive caching with machine learned advicecited by 194
  2. 2017The Case for Learned Index Structurescited by 188
  3. 2017Revenue Optimization with Approximate Bid Predictionscited by 21
  4. 2014Competitive Algorithms from Competitive Equilibria: Non-Clairvoyant Scheduling under Polyhedral Constraintscited by 4
  5. 2014SELFISHMIGRATE: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processorscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 9; 2025: 28; 2026: 28.

65 papers.

Sort:

  1. 2024Binary Search with Distributional Predictionscited by 11
  2. 2024Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithmscited by 8
  3. 2025Learning-Augmented Online Bipartite Fractional Matchingcited by 8
  4. 2024Learning-Augmented Algorithms for the Bahncard Problemcited by 7
  5. 2025On Tradeoffs in Learning-Augmented Algorithmscited by 7
  6. 2025Algorithms with Calibrated Machine Learning Predictionscited by 7
  7. 2026Scheduling LLM Inference with Uncertainty-Aware Output Length Predictionscited by 7
  8. 2024Learning-Augmented Robust Algorithmic Recoursecited by 4
  9. 2024Learning multivariate Gaussians with imperfect advicecited by 4
  10. 2025Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Searchcited by 4
  11. 2025Approximate Proportionality in Online Fair Divisioncited by 4
  12. 2025Learning to Price with Resource Constraints: From Full Information to Machine-Learned Pricescited by 3
38 more
  1. 2025Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistencycited by 3
  2. 2025Learning-Augmented Online Bidding in Stochastic Settingscited by 3
  3. 2024Fast and Reliable N-k Contingency Screening with Input-Convex Neural Networkscited by 2
  4. 2025Efficiently Solving Discounted MDPs with Predictions on Transition Matricescited by 2
  5. 2025Learning-Augmented Online Bipartite Matching in the Random Arrival Order Modelcited by 2
  6. 2026The Secretary Problem with Predictions and a Chosen Ordercited by 2
  7. 2026Ski Rental with Distributional Predictions of Unknown Qualitycited by 2
  8. 2026Multi-Armed Bandits With Best-Action Queriescited by 2
  9. 2024On Approximability of ℓ22 Min-Sum Clusteringcited by 1
  10. 2025Learning-Augmented Algorithms for Boolean Satisfiabilitycited by 1
  11. 2025Optimizing Health Coverage in Ethiopia: A Learning-augmented Approach and Persistent Proportionality Under an Online Budgetcited by 1
  12. 2025Learning-Augmented Streaming Algorithms for Correlation Clusteringcited by 1
  13. 2025Product distribution learning with imperfect advicecited by 1
  14. 2025Online Smoothed Demand Managementcited by 1
  15. 2025Learning-Augmented Ski Rental with Discrete Distributions: A Bayesian Approachcited by 1
  16. 2026Learning-augmented smooth integer programs with PAC-learnable oraclescited by 1
  17. 2026Parsimonious Learning-Augmented Online Metric Matchingcited by 1
  18. 2026Learning-Augmented Online Minimization with Dual Predictionscited by 1
  19. 2024Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraintscited by 0
  20. 2024Safe Exploitative Play with Untrusted Type Beliefscited by 0
  21. 2025Decision-Theoretic Approaches for Improved Learning-Augmented Algorithmscited by 0
  22. 2025Prediction-Augmented Mechanism Design for Weighted Facility Locationcited by 0
  23. 2025On multiagent online problems with predictionscited by 0
  24. 2025Competitive Algorithms for Multi-Agent Ski-Rental Problemscited by 0
  25. 2025Smoothed Online Optimization for Target Tracking: Robust and Learning-Augmented Algorithmscited by 0
  26. 2025Signal-Aware Workload Shifting Algorithms with Uncertainty-Quantified Predictorscited by 0
  27. 2025Transductive and Learning-Augmented Online Regressioncited by 0
  28. 2025Prediction-Specific Design of Learning-Augmented Algorithmscited by 0
  29. 2025Impartial Selection with Predictionscited by 0
  30. 2025Online Multi-Class Selection with Group Fairness Guaranteecited by 0
  31. 2025A Switching Framework for Online Interval Scheduling with Predictionscited by 0
  32. 2025Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimizationcited by 0
  33. 2026Analyzing the effect of prediction accuracy on the distributionally-robust competitive ratiocited by 0
  34. 2026Online Algorithms with Unreliable Guidancecited by 0
  35. 2026Robust and Consistent Ski Rental with Distributional Advicecited by 0
  36. 2026Learning Unanimously Acceptable Lotteries via Queriescited by 0
  37. 2026Resilient Byzantine Agreement with Predictionscited by 0
  38. 2026Learning-Augmented Online Scheduling with Parsimonious Preemptioncited by 0

50 most cited of 65 All 65 (JSON)