2021/10/01 by Nguyễn Kim Thắng, Thang, Nguyen Kim, Christoph Dürr +1
Computer Science · Decision Sciences · #Auction Theory and Applications #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2110.00391
openalex publication_date 2021/10/01 · openalex created_date 2021/10/11 · openalex updated_date 2026/07/28
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.