论文标题
数据驱动的在线背包的竞争算法和设置封面
Data-driven Competitive Algorithms for Online Knapsack and Set Cover
论文作者
论文摘要
在线算法的设计倾向于专注于具有最差保证的算法，例如竞争比率的界限。然而，众所周知，这种算法通常过于悲观，在非顽固的输入上表现出色。在本文中，我们开发了一种用于在线算法的数据驱动设计的方法，该方法维持近乎最佳的最差案例保证，同时还可以进行学习，以便为典型的输入表现良好。我们的方法是确定承认全球最差案例保证的政策类，然后在策略类中使用历史数据进行学习。我们在两个经典问题的背景下演示了这种方法，即在线背包和在线套装，在每种情况下都证明了丰富的政策类别的竞争界限。此外，我们通过对电动汽车充电的案例研究说明了实际含义。
The design of online algorithms has tended to focus on algorithms with worst-case guarantees, e.g., bounds on the competitive ratio. However, it is well-known that such algorithms are often overly pessimistic, performing sub-optimally on non-worst-case inputs. In this paper, we develop an approach for data-driven design of online algorithms that maintain near-optimal worst-case guarantees while also performing learning in order to perform well for typical inputs. Our approach is to identify policy classes that admit global worst-case guarantees, and then perform learning using historical data within the policy classes. We demonstrate the approach in the context of two classical problems, online knapsack and online set cover, proving competitive bounds for rich policy classes in each case. Additionally, we illustrate the practical implications via a case study on electric vehicle charging.
