mlsanityData to 7 Oct 2026

Online Algorithms with Multiple Predictions

arXiv 2205.03921 ↗First posted 8 May 2022cs.LG cs.DScited by 22

Not on the map. Why?

Abstract (arXiv)

This paper studies online algorithms augmented with multiple machine-learned predictions. While online algorithms augmented with a single prediction have been extensively studied in recent years, the literature for the multiple predictions setting is sparse. In this paper, we give a generic algorithmic framework for online covering problems with multiple predictions that obtains an online solution that is competitive against the performance of the best predictor. Our algorithm incorporates the use of predictions in the classic potential-based analysis of online algorithms. We apply our algorithmic framework to solve classical problems such as online set cover, (weighted) caching, and online facility location in the multiple predictions setting. Our algorithm can also be robustified, i.e., the algorithm can be simultaneously made competitive against the best prediction and the performance of the best online algorithm (without prediction).

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 23 of its 60 references that are in the map. First posted on arXiv 8 May 2022.

Builds on

23 of 60 references.

References · 23

  1. 2018Competitive caching with machine learned advicecited by 194
  2. 2020The Primal-Dual method for Learning Augmented Algorithmscited by 78
  3. 2020Online metric algorithms with untrusted predictionscited by 74
  4. 2020Secretary and Online Matching Problems with Machine Learned Advicecited by 71
  5. 2019A Model for Learned Bloom Filters, and Optimizing by Sandwichingcited by 64
  6. 2020Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithmscited by 64
  7. 2019Scheduling with Predictions and the Price of Mispredictioncited by 45
  8. 2019Learning-Based Low-Rank Approximationscited by 41
  9. 2020Secretaries with Advicecited by 41
  10. 2020Better and Simpler Learning-Augmented Online Cachingcited by 38
  11. 2020Learning Augmented Energy Minimization via Speed Scalingcited by 38
  12. 2020Online Learning with Imperfect Hintscited by 37
11 more
  1. 2020Online Algorithms for Weighted Paging with Predictionscited by 29
  2. 2021Flow Time Scheduling with Uncertain Processing Timecited by 29
  3. 2020Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancingcited by 27
  4. 2021Online Graph Algorithms with Predictionscited by 25
  5. 2017Revenue Optimization with Approximate Bid Predictionscited by 21
  6. 2021Learning-based Support Estimation in Sublinear Timecited by 16
  7. 2020Online Linear Optimization with Many Hintscited by 15
  8. 2021Online Facility Location with Predictionscited by 14
  9. 2018k-Servers with a Smile: Online Algorithms via Projectionscited by 3
  10. 2018On Approximating (Sparse) Covering Integer Programscited by 2
  11. 2021Online metric allocationcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 6; 2024: 9; 2025: 3; 2026: 2.

22 papers.

Sort:

  1. 2022Algorithms with Prediction Portfolioscited by 19
  2. 2023Sorting with Predictionscited by 14
  3. 2023Mixing predictions for online metric algorithmscited by 12
  4. 2022Learning-Augmented Algorithms for Online Linear and Semidefinite Programmingcited by 11
  5. 2024Binary Search with Distributional Predictionscited by 11
  6. 2023Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictionscited by 8
  7. 2024Learning-Augmented Algorithms with Explicit Predictorscited by 8
  8. 2024Contract Scheduling with Distributional and Multiple Advicecited by 8
  9. 2024Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithmscited by 8
  10. 2023Minimalistic Predictions to Schedule Jobs with Online Precedence Constraintscited by 7
  11. 2024Learning-Augmented Algorithms for the Bahncard Problemcited by 7
  12. 2024Learning-Augmented Search Data Structurescited by 4
10 more
  1. 2024Competitive strategies to use "warm start" algorithms with predictionscited by 4
  2. 2025Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictorscited by 2
  3. 2023Out-of-Distribution-Aware Electric Vehicle Chargingcited by 1
  4. 2023Online Covering with Multiple Expertscited by 1
  5. 2024On Approximability of ℓ22 Min-Sum Clusteringcited by 1
  6. 2026Learning-Augmented Online Minimization with Dual Predictionscited by 1
  7. 2024The SMART approach to instance-optimal online learningcited by 0
  8. 2025On multiagent online problems with predictionscited by 0
  9. 2025Transductive and Learning-Augmented Online Regressioncited by 0
  10. 2026Robust and Consistent Ski Rental with Distributional Advicecited by 0