Datensatz

Zusammenfassung

The classical analysis of online algorithms, due to its worst-case nature,
can be quite pessimistic when the input instance at hand is far from
worst-case. Often this is not an issue with machine learning approaches, which
shine in exploiting patterns in past inputs in order to predict the future.
However, such predictions, although usually accurate, can be arbitrarily poor.
Inspired by a recent line of work, we augment three well-known online settings
with machine learned predictions about the future, and develop algorithms that
take them into account. In particular, we study the following online selection
problems: (i) the classical secretary problem, (ii) online bipartite matching
and (iii) the graphic matroid secretary problem. Our algorithms still come with
a worst-case performance guarantee in the case that predictions are subpar
while obtaining an improved competitive ratio (over the best-known classical
online algorithm for each problem) when the predictions are sufficiently
accurate. For each algorithm, we establish a trade-off between the competitive
ratios obtained in the two respective cases.