Online Primal-Dual Algorithms with Predictions for Non-Linear Packing/Covering Problems

The domain of online algorithms with predictions has been extensively studied with new algorithms designed for different problems of scheduling, caching (paging), clustering, ski rental, etc. Recently, Bamas et al., aiming for an unified method, has 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 problems with packing/covering contraints. We illustrate the applicability of our framework through several important problems such as submodular maximization/minimization, energy minimization, load balancing.