# Online Primal-Dual Algorithms with Predictions for Packing Problems

arXiv: https://arxiv.org/abs/2110.00391 · HTML: https://mlsanity.com/paper/2110.00391/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 36 references that are in the map.
- First posted on arXiv 1 Oct 2021.

## Builds on (most cited first, 15 of 15)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [Scheduling with Predictions and the Price of Misprediction](https://mlsanity.com/paper/1902.00732/) (2019)
- [Online Computation with Untrusted Advice](https://mlsanity.com/paper/1905.05655/) (2019)
- [Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing](https://mlsanity.com/paper/2011.11743/) (2020)
- [Continuous DR-submodular Maximization: Structure and Algorithms](https://mlsanity.com/paper/1711.02515/) (2017)
- [Semi-Online Bipartite Matching](https://mlsanity.com/paper/1812.00134/) (2018)
- [Online Contention Resolution Schemes](https://mlsanity.com/paper/1508.00142/) (2015)
- [Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models](https://mlsanity.com/paper/1711.05764/) (2017)
- [Beyond Worst-Case Analysis](https://mlsanity.com/paper/1806.09817/) (2018)
- [Online Primal-Dual Algorithms with Configuration Linear Programs](https://mlsanity.com/paper/1708.04903/) (2017)

## Built on by (most cited first, 3 of 3)

- [Learning-Augmented Algorithms for Online Linear and Semidefinite Programming](https://mlsanity.com/paper/2209.10614/) (2022)
- [A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives](https://mlsanity.com/paper/2406.03574/) (2024)
- [Compressing Value Predictions for Learning-Augmented Metrical Task Systems](https://mlsanity.com/paper/2609.33580/) (2026)

## Abstract (arXiv)

The domain of online algorithms with predictions has been extensively studied for different applications such as scheduling, caching (paging), clustering, ski rental, etc. Recently, Bamas et al., aiming for an unified method, have provided a primal-dual framework for linear covering problems. They extended the online primal-dual method by incorporating predictions in order to achieve a performance beyond the worst-case case analysis. In this paper, we consider this research line and present a framework to design algorithms with predictions for non-linear packing problems. We illustrate the applicability of our framework in submodular maximization and in particular ad-auction maximization in which the optimal bound is given and supporting experiments are provided.