Secretary and Online Matching Problems with Machine Learned Advice
Secretary and Online Matching Problems with Machine Learned Advice
复制标题
DOI：
10.1016/j.disopt.2023.100778
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
A. Antoniadis;Themis Gouleakis;P. Kleer;Pavel Kolev
中科院分区：
文献类型：
--
作者：
A. Antoniadis;Themis Gouleakis;P. Kleer;Pavel Kolev
在线算法的经典分析由于其最坏情况的性质，当手头的输入实例远非最坏情况时，可能会非常悲观。相比之下，机器学习方法的亮点在于利用过去输入的模式来预测未来。然而，这样的预测虽然通常是准确的，但也可能很差。受到最近一系列工作的启发，我们通过机器学习对未来的预测来增强三个众所周知的在线设置，并开发考虑这些预测的算法。我们特别研究了以下在线选择问题：（i）经典秘书问题，（ii）在线二分匹配和（iii）图形拟阵秘书问题。我们的算法在预测低于标准的情况下仍然提供最坏情况的性能保证，同时在预测足够准确时获得改进的竞争比（相对于每个问题的最著名的经典在线算法）。对于每种算法，我们在两种情况下获得的竞争比之间建立权衡。
The classic analysis of online algorithms, due to its worst-case nature, can be quite pessimistic when the input instance at hand is far from worst-case. In contrast, machine learning approaches shine in exploiting patterns in past inputs in order to predict the future. However, such predictions, although usually accurate, can be arbitrarily poor. Inspired by a recent line of work, we augment three well-known online settings with machine learned predictions about the future, and develop algorithms that take these predictions into account. In particular, we study the following online selection problems: (i) the classic secretary problem, (ii) online bipartite matching and (iii) the graphic matroid secretary problem. Our algorithms still come with a worst-case performance guarantee in the case that predictions are subpar while obtaining an improved competitive ratio (over the best-known classic online algorithm for each problem) when the predictions are sufficiently accurate. For each algorithm, we establish a trade-off between the competitive ratios obtained in the two respective cases.