Online algorithms with predictions is a popular and elegant framework for
bypassing pessimistic lower bounds in competitive analysis. In this model,
online algorithms are supplied with future predictions, and the goal is for the
competitive ratio to smoothly interpolate between the best offline and online
bounds as a function of the prediction error. In this paper, we study online
graph problems with predictions. Our contributions are the following:
* The first question is defining prediction error. For graph/metric problems,
there can be two types of error, locations that are not predicted, and
locations that are predicted but the predicted and actual locations do not
coincide exactly. We design a novel definition of prediction error called
metric error with outliers to simultaneously capture both types of errors,
which thereby generalizes previous definitions of error that only capture one
of the two error types.
* We give a general framework for obtaining online algorithms with
predictions that combines, in a "black box" fashion, existing online and
offline algorithms, under certain technical conditions. To the best of our
knowledge, this is the first general-purpose tool for obtaining online
algorithms with predictions.
* Using our framework, we obtain tight bounds on the competitive ratio of
several classical graph problems as a function of metric error with outliers:
Steiner tree, Steiner forest, priority Steiner tree/forest, and
uncapacitated/capacitated facility location.
Both the definition of metric error with outliers and the general framework
for combining offline and online algorithms are not specific to the problems
that we consider in this paper. We hope that these will be useful for future
work in this domain.

本文研究具有预测的在线图形问题，提出了一个新的度量误差的定义 (metric error)，并给出了一个通用框架，用于在线预测算法。采用这个框架，我们能够获得关于竞争比率的紧密限制，并将其作为度量误差的函数来描述。