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.
翻译:最近,Bamas等人为了采用统一的方法,为线性覆盖问题提供了一个原始的双重框架,它们扩大了在线初线覆盖方法的范围,将预测纳入其中,以便实现超出最坏案例分析的性能。在本文件中,我们考虑了这一研究线,并提出了一个框架,用以设计带有非线性包装问题预测的算法。我们举例说明了我们框架在次模式最大化中的适用性,特别是提供最佳约束和支持实验的自动优化最大化。