mlsanityData to 14 Oct 2026

The Primal-Dual method for Learning Augmented Algorithms

arXiv 2010.11632 ↗First posted 22 Oct 2020cs.LG cs.DScited by 80

Not on the map. Why?

Abstract (arXiv)

The extension of classical online algorithms when provided with predictions is a new and active research area. In this paper, we extend the primal-dual method for online algorithms in order to incorporate predictions that advise the online algorithm about the next action to take. We use this framework to obtain novel algorithms for a variety of online covering problems. We compare our algorithms to the cost of the true and predicted offline optimal solutions and show that these algorithms outperform any online algorithm when the prediction is accurate while maintaining good guarantees when the prediction is misleading.

Key facts. Cited by 80 papers in the map (data through 14 Oct 2026). First posted on arXiv 22 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 7; 2022: 15; 2023: 16; 2024: 20; 2025: 9; 2026: 13.

80 papers.

Sort:

By area:

  1. 2021Faster Matchings via Learned Dualscited by 56
  2. 2022Learning Predictions for Algorithms with Predictionscited by 25
  3. 2022Permutation Predictions for Non-Clairvoyant Schedulingcited by 22
  4. 2022Online Algorithms with Multiple Predictionscited by 22
  5. 2022Triangle and Four Cycle Counting with Predictions in Graph Streamscited by 20
  6. 2021Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problemscited by 19
  7. 2022Parsimonious Learning-Augmented Cachingcited 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. 2024Online bipartite matching with imperfect advicecited by 13
38 more
  1. 2022A Regression Approach to Learning-Augmented Online Algorithmscited by 12
  2. 2022Learning-Augmented Algorithms for Online Linear and Semidefinite Programmingcited by 11
  3. 2024Learning-augmented Maximum Independent Setcited by 11
  4. 2024Binary Search with Distributional Predictionscited by 11
  5. 2021Double Coverage with Machine-Learned Advicecited by 10
  6. 2022Smoothed Online Optimization with Unreliable Predictionscited by 10
  7. 2023Active causal structure learning with advicecited by 10
  8. 2023Online Algorithms with Uncertainty-Quantified Predictionscited by 9
  9. 2022Learning-Augmented Algorithms for Online TSP on the Linecited by 8
  10. 2023Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictionscited by 8
  11. 2024Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithmscited by 8
  12. 2023Minimalistic Predictions to Schedule Jobs with Online Precedence Constraintscited by 7
  13. 2023Online Ad Allocation with Predictionscited by 7
  14. 2024Non-clairvoyant Scheduling with Partial Predictionscited by 7
  15. 2024Learning-Augmented Priority Queuescited by 7
  16. 2024Learning-Augmented Algorithms for the Bahncard Problemcited by 7
  17. 2025On Tradeoffs in Learning-Augmented Algorithmscited by 7
  18. 2021Learning-Augmented Algorithms for Online Steiner Treecited by 6
  19. 2022Scheduling with Speed Predictionscited by 6
  20. 2021Improved Bounds for Online Facility Location with Predictionscited by 5
  21. 2022Contextual Pandora's Boxcited by 5
  22. 2022Learning-Augmented Private Algorithms for Multiple Quantile Releasecited by 5
  23. 2023Online Dynamic Acknowledgement with Learned Predictionscited by 5
  24. 2024Online Classification with Predictionscited by 5
  25. 2024Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problemscited by 5
  26. 2023The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformationscited by 4
  27. 2024Learning-Augmented Search Data Structurescited by 4
  28. 2024Learning-Based Algorithms for Graph Searching Problemscited by 4
  29. 2024Learning multivariate Gaussians with imperfect advicecited by 4
  30. 2025Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Searchcited by 4
  31. 2025Approximate Proportionality in Online Fair Divisioncited by 4
  32. 2021Online Primal-Dual Algorithms with Predictions for Packing Problemscited by 3
  33. 2023Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster L-/L^natural-Convex Function Minimizationcited by 3
  34. 2023A Survey of Machine Learning-Based Ride-Hailing Planningcited by 3
  35. 2023Faster Discrete Convex Function Minimization with Predictions: The M-Convex Casecited by 3
  36. 2024Learning-augmented Online Algorithm for Two-level Ski-rental Problemcited by 3
  37. 2025Learning-Augmented Online Bidding in Stochastic Settingscited by 3
  38. 2023On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rentalcited by 2

50 most cited of 80 All 80 (JSON)