mlsanityData to 7 Oct 2026

Algorithms with Predictions

arXiv 2006.09123 ↗First posted 16 Jun 2020cs.DScited by 152

Not on the map. Why?

Abstract (arXiv)

We introduce algorithms that use predictions from machine learning applied to the input to circumvent worst-case analysis. We aim for algorithms that have near optimal performance when these predictions are good, but recover the prediction-less worst case behavior when the predictions have large errors.

Key facts. Cited by 152 papers in the map (data through 7 Oct 2026). First posted on arXiv 16 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 22; 2023: 23; 2024: 29; 2025: 33; 2026: 33.

152 papers.

Sort:

By area:

  1. 2021Faster Matchings via Learned Dualscited by 56
  2. 2023Learning to Warm-Start Fixed-Point Optimization Algorithmscited by 32
  3. 2021Learning-Augmented k-means Clusteringcited by 26
  4. 2022Learning Predictions for Algorithms with Predictionscited by 25
  5. 2022Generalization Bounds for Data-Driven Numerical Linear Algebracited by 24
  6. 2021Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Boundscited by 20
  7. 2022Triangle and Four Cycle Counting with Predictions in Graph Streamscited by 20
  8. 2022Parsimonious Learning-Augmented Cachingcited by 19
  9. 2022Algorithms with Prediction Portfolioscited by 19
  10. 2021A Novel Prediction Setup for Online Speed-Scalingcited by 17
  11. 2022Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictionscited by 16
  12. 2023Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysiscited by 16
38 more
  1. 2023Sorting with Predictionscited by 14
  2. 2021Can Q-Learning be Improved with Advice?cited by 13
  3. 2021Robust Learning-Augmented Caching: An Experimental Studycited by 12
  4. 2024Algorithms for Caching and MTS with reduced number of predictionscited by 12
  5. 2021Online Bin Packing with Predictionscited by 11
  6. 2021(Optimal) Online Bipartite Matching with Degree Informationcited by 11
  7. 2022Learning-Augmented Maximum Flowcited by 11
  8. 2024Learning-augmented Maximum Independent Setcited by 11
  9. 2024Binary Search with Distributional Predictionscited by 11
  10. 2022Paging with Succinct Predictionscited by 10
  11. 2022Improved Learning-augmented Algorithms for k-means and k-medians Clusteringcited by 10
  12. 2023Active causal structure learning with advicecited by 10
  13. 2024Algorithm Configuration for Structured Pfaffian Settingscited by 10
  14. 2022Single-Leg Revenue Management with Advicecited by 9
  15. 2022Label Propagation with Weak Supervisioncited by 9
  16. 2023Online Algorithms with Uncertainty-Quantified Predictionscited by 9
  17. 2022Learning-Augmented Algorithms for Online TSP on the Linecited by 8
  18. 2023Meta-Learning Adversarial Bandit Algorithmscited by 8
  19. 2023Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictionscited by 8
  20. 2024Learning-Augmented Algorithms with Explicit Predictorscited by 8
  21. 2024Contract Scheduling with Distributional and Multiple Advicecited by 8
  22. 2024Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithmscited by 8
  23. 2025What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimizationcited by 8
  24. 2022A Nearly Tight Analysis of Greedy k-means++cited by 7
  25. 2023Minimalistic Predictions to Schedule Jobs with Online Precedence Constraintscited by 7
  26. 2023Online Ad Allocation with Predictionscited by 7
  27. 2024Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cutcited by 7
  28. 2024Non-clairvoyant Scheduling with Partial Predictionscited by 7
  29. 2024Learning-Augmented Priority Queuescited by 7
  30. 2024Learning-Augmented Algorithms for the Bahncard Problemcited by 7
  31. 2025Algorithms with Calibrated Machine Learning Predictionscited by 7
  32. 2025Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithmscited by 7
  33. 2026Scheduling LLM Inference with Uncertainty-Aware Output Length Predictionscited by 7
  34. 2022Scheduling with Speed Predictionscited by 6
  35. 2022Online Learning and Bandits with Queried Hintscited by 6
  36. 2021Improved Bounds for Online Facility Location with Predictionscited by 5
  37. 2022Meta-Learning Adversarial Banditscited by 5
  38. 2022Learning-Augmented Private Algorithms for Multiple Quantile Releasecited by 5

50 most cited of 152 All 152 (JSON)