Data-driven Competitive Algorithms for Online Knapsack and Set Cover
Data-driven Competitive Algorithms for Online Knapsack and Set Cover
复制标题
DOI：
10.1609/aaai.v35i12.17294
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Ali Zeynali;Bo Sun;M. Hajiesmaili;A. Wierman
中科院分区：
文献类型：
--
作者：
Ali Zeynali;Bo Sun;M. Hajiesmaili;A. Wierman
在线算法的设计倾向于关注具有最坏情况保证的算法，例如，竞争力的比例。然而，众所周知，这样的算法通常过于悲观，在非最坏情况下的输入上执行次优。在本文中，我们开发了一种在线算法的数据驱动设计方法，该方法保持接近最优的最坏情况保证，同时还进行学习，以便在典型输入下表现良好。我们的方法是确定承认全球最坏情况下的保证政策类，然后使用历史数据进行学习的政策类。我们展示了两个经典的问题，在线背包和在线集覆盖的背景下，证明在每种情况下丰富的政策类的竞争范围的方法。此外，我们通过电动汽车充电的案例研究说明了实际意义。
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.