Secretary and Online Matching Problems with Machine Learned Advice

There has been enormous progress in the field of machine learning in the last decade, which has affected a variety of other areas as well. One of these areas is the design of online algorithms. Traditionally, the analysis of such algorithms involves worst-case guarantees, which can often be quite pessimistic. It is conceivable though, that having prior knowledge regarding the online input (obtained using machine learning) could potentially improve those guarantees significantly. In this work, we consider various online selection algorithms augmented with so-called machine learned advice. In particular, we consider secretary and online bipartite matching problems. The high-level idea is to incorporate some form of predictions in an existing online algorithm in order to get the best of two worlds: (i) provably improve the algorithm's performance guarantee in the case that predictions are sufficiently good, while (ii) losing only a constant factor of the algorithm's existing Work done in part while the author was at Saarland University and Max-Planck-Institute for Informatics and supported by DFG grant AN 1262/1-1.