论文标题
部分可观测时空混沌系统的无模型预测
Canadian Traveller Problem with Predictions
论文作者
论文摘要
在这项工作中，我们考虑了Lykouris＆Vassilvitskii建议的$ K $ - 加拿大旅行者问题（$ K $ -CTP）。 $ K $ -CTP是最短路径问题的概括，涉及一个旅行者，他提前知道整个图表，并希望找到从源顶点$ s $到目标顶点$ t $的最短路线，但在线发现某些边缘（高达$ k $）被阻止了它们。潜在的不完善的预测变量为我们提供了阻塞边缘的数量和位置。 我们提供了一种确定性和随机在线算法，用于学习增强的$ k $ -CTP，该算法在一致性（预测正确时解决方案的质量）和鲁棒性（在预测中存在错误时解决方案的质量）之间实现了权衡。此外，我们证明了确定性案例的匹配下限，该案例确定一致性和鲁棒性之间的权衡是最佳的，并显示了随机算法的下限。最后，我们证明了$ K $ -CTP的竞争比率的几个确定性和随机下限，具体取决于预测错误，并在大多数情况下以匹配的上限进行补充。
In this work, we consider the $k$-Canadian Traveller Problem ($k$-CTP) under the learning-augmented framework proposed by Lykouris & Vassilvitskii. $k$-CTP is a generalization of the shortest path problem, and involves a traveller who knows the entire graph in advance and wishes to find the shortest route from a source vertex $s$ to a destination vertex $t$, but discovers online that some edges (up to $k$) are blocked once reaching them. A potentially imperfect predictor gives us the number and the locations of the blocked edges. We present a deterministic and a randomized online algorithm for the learning-augmented $k$-CTP that achieve a tradeoff between consistency (quality of the solution when the prediction is correct) and robustness (quality of the solution when there are errors in the prediction). Moreover, we prove a matching lower bound for the deterministic case establishing that the tradeoff between consistency and robustness is optimal, and show a lower bound for the randomized algorithm. Finally, we prove several deterministic and randomized lower bounds on the competitive ratio of $k$-CTP depending on the prediction error, and complement them, in most cases, with matching upper bounds.
