Abstract:
The extension of classical online algorithms when provided with predictions is
a new and active research area. In this paper, we extend the primal-dual method
for online algorithms in order to incorporate predictions that advise the online
algorithm about the next action to take. We use this framework to obtain novel
algorithms for a variety of online covering problems. We compare our algorithms
to the cost of the true and predicted offline optimal solutions and show that these
algorithms outperform any online algorithm when the prediction is accurate while
maintaining good guarantees when the prediction is misleading.
