This paper considers the recently popular beyond-worst-case algorithm analysis model which integrates machine-learned predictions with online algorithm design. We consider the online Steiner tree problem in this model for both directed and undirected graphs. Steiner tree is known to have strong lower bounds in the online setting and any algorithm's worst-case guarantee is far from desirable. This paper considers algorithms that predict which terminal arrives online. The predictions may be incorrect and the algorithms' performance is parameterized by the number of incorrectly predicted terminals. These guarantees ensure that algorithms break through the online lower bounds with good predictions and the competitive ratio gracefully degrades as the prediction error grows. We then observe that the theory is predictive of what will occur empirically. We show on graphs where terminals are drawn from a distribution, the new online algorithms have strong performance even with modestly correct predictions.
翻译:本文审视了最近流行的将机学预测与在线算法设计相结合的超坏情况算法分析模型。 我们认为,在这个模型中,定向图和非定向图都存在在线施泰纳树问题。 施泰纳树已知在在线设置中有很强的下限, 任何算法最坏情况的保证都远远不可取。 本文审视了预测哪些终端抵达网上的算法。 预测可能不正确, 算法的性能也以错误预测终端的数量为参数。 这些保证确保了算法在网上下限中突破, 并随着预测错误的增加而出现良好的预测和竞争性的优减率。 然后我们观察到, 理论是实验性地预测会发生什么。 我们在图表中显示从分布中提取终端的图表, 新的在线算法的性能是很强的, 即使有微小的准确预测。