标题： 用于在线凹包问题和凸覆盖问题的学习增强算法 显示英文标题

标题： Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems

摘要： 学习增强算法近年来在计算机科学界得到了广泛研究，这是由机器学习预测器的进步所推动的，这些预测器可以提供额外信息来增强经典算法。 这样的预测在在线问题的背景下特别有效，因为在这些问题中，决策必须在不了解未来的情况下做出，而传统上这些问题表现出限制任何在线算法性能的不可能性结果。 因此，学习增强算法的研究旨在谨慎地使用外部建议，在建议准确时克服经典不可能性结果，并且即使建议不准确时，也能与最先进的在线算法表现相当。 在本文中，我们提出了两种基本优化设置的学习增强算法框架，扩展并推广了之前的工作。 对于具有凹目标的在线包装问题，我们提出了一种简单但全面的策略，该策略在建议和最先进的在线算法之间切换。 对于具有凸目标的在线覆盖问题，我们大大扩展了Azar等人（FOCS 2016）针对在线凸覆盖程序的原始对偶方法，以及文献中先前的在线覆盖线性规划的学习增强框架，以应用于许多新的应用。 我们证明，当建议准确时，我们的算法能够打破不可能性结果，而在建议有误时，仍能保持与最先进的经典在线算法相当的性能。 显示英文摘要

摘要： Learning-augmented algorithms have been extensively studied across the computer science community in the recent years, driven by advances in machine learning predictors, which can provide additional information to augment classical algorithms. Such predictions are especially powerful in the context of online problems, where decisions have to be made without knowledge of the future, and which traditionally exhibits impossibility results bounding the performance of any online algorithm. The study of learning-augmented algorithms thus aims to use external advice prudently, to overcome classical impossibility results when the advice is accurate, and still perform comparably to the state-of-the-art online algorithms even when the advice is inaccurate. In this paper, we present learning-augmented algorithmic frameworks for two fundamental optimizations settings, extending and generalizing prior works. For online packing with concave objectives, we present a simple but overarching strategy that switches between the advice and the state-of-the-art online algorithm. For online covering with convex objectives, we greatly extend primal-dual methods for online convex covering programs by Azar et al. (FOCS 2016) and previous learning-augmented framework for online covering linear programs from the literature, to many new applications. We show that our algorithms break impossibility results when the advice is accurate, while maintaining comparable performance with state-of-the-art classical online algorithms even when the advice is erroneous.