Learning Augmented Online Facility Location

Online algorithms is a field that deals with algorithmic problems in which the input is not entirely known in advance, but rather arrives in a sequential way. The algorithm is required to make irrevocable decisions, only based on the input received at a given point, and to incur the corresponding irrevocable cost for each of them. Traditionally, in the analysis of online algorithms we assume, rather pessimistically, that an adversary always presents the algorithm with the worst case input. More precisely, the performance of online algorithms is evaluated by the competitive ratio [5], which is the worst-case ratio of total algorithm's cost to the cost of a computationally unlimited optimal algorithm that is aware of the entire request sequence in advance. On the other hand, one of the main goals in the field of machine learning is to predict the unknown based on data, and learn what the world looks like, rather than preparing for the worst that can happen. In an effort to exploit this, there has been a trend in recent years that tries to use machine learning predictions in order to deal with the inherent uncertainty in online algorithms, while still providing worst case performance guarantees. Specifically, one might think that directly using machine learning in online problems should enhance their performance, since by knowing, with some error, how the input looks like, we should be able to come up with almost optimal solutions/approximations. In reality, this turns out not to be true, since the error of the learner does not necessarily remain constant, and it could propagate during different phases of the algorithm and cause a much bigger error. In a recent work, Lykouris and Vassilvitski [4] tried to formulate a framework to provide formal guarantees for these learning augmented online algorithms, in terms of consistency and robustness.