# A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 50 references that are in the map.
- First posted on arXiv 5 Jun 2024.

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

- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Online Learning: A Comprehensive Survey](https://mlsanity.com/paper/1802.02871/) (2018)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [Faster Fundamental Graph Algorithms via Learned Predictions](https://mlsanity.com/paper/2204.12055/) (2022)
- [Secretaries with Advice](https://mlsanity.com/paper/2011.06726/) (2020)
- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (2021)
- [A Deep Information Sharing Network for Multi-contrast Compressed Sensing MRI Reconstruction](https://mlsanity.com/paper/1804.03596/) (2018)
- [Triangle and Four Cycle Counting with Predictions in Graph Streams](https://mlsanity.com/paper/2203.09572/) (2022)
- [Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model](https://mlsanity.com/paper/2206.11397/) (2022)
- [Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging](https://mlsanity.com/paper/2010.00412/) (2020)
- [Online Facility Location with Predictions](https://mlsanity.com/paper/2110.08840/) (2021)
- [Learning-Augmented Algorithms for Online Linear and Semidefinite Programming](https://mlsanity.com/paper/2209.10614/) (2022)
- [Large-Scale Convex Optimization for Dense Wireless Cooperative Networks](https://mlsanity.com/paper/1506.00749/) (2015)
- [Competitive Online Optimization under Inventory Constraints](https://mlsanity.com/paper/1901.09161/) (2019)
- [The Competitive Ratio of Threshold Policies for Online Unit-density Knapsack Problems](https://mlsanity.com/paper/1907.08735/) (2019)
- [Online Unit Profit Knapsack with Untrusted Predictions](https://mlsanity.com/paper/2203.00285/) (2022)
- [Online Primal-Dual Algorithms with Predictions for Packing Problems](https://mlsanity.com/paper/2110.00391/) (2021)
- [Online Network Utility Maximization: Algorithm, Competitive Analysis, and Applications](https://mlsanity.com/paper/2101.10898/) (2021)
- [Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problems](https://mlsanity.com/paper/2402.08701/) (2024)

## Abstract (arXiv)

Learning-augmented algorithms has been extensively studied recently in the computer-science community, due to the potential of using machine learning predictions in order to improve the performance of algorithms. Predictions are especially useful for online algorithms making irrevocable decisions without knowledge of the future. Such learning-augmented algorithms aim to overcome the limitations of classical online algorithms when the predictions are accurate, and still perform comparably when the predictions are inaccurate. A common approach is to adapt existing online algorithms to the particular advice notion employed, which often involves understanding previous sophisticated algorithms and their analyses. However, ideally, one would simply use previous online solutions in a black-box fashion, without much loss in the approximation guarantees. Such clean solutions that avoid opening up black-boxes are often rare, and may be even missed the first time around. For example, Grigorescu et al. (NeurIPS 22) proposed a learning-augmented algorithms for online covering linear programs, but it later turned out that their results can be subsumed by a natural approach that switches between the advice and an online algorithm given as a black-box, as noted in their paper. In this work, we introduce and analyze a simple learning-augmented algorithm for online packing problems with linear constraints and concave objectives. We exhibit several direct applications of our framework including online packing linear programming, knapsack, resource management benefit, throughput maximization, and network utility maximization. We further raise the problem of understanding necessary and sufficient conditions for when such simple black-box solutions may be optimal. We believe this is an important direction of research that would unify many ad-hoc approaches from the literature.