Secretary and Online Matching Problems with Machine Learned Advice

By Antonios Foivos Antoniadis, Themis Gouleakis, Pieter Kleer, Pavel Kolev. 2020

163 citations recorded by the source corpus.

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.

Subfields: Computer Networks and Communications, Management Science and Operations Research, Statistical Learning Theory, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

1. Simon Lacoste-Julien
2. Pascal Vincent
3. Hugo Berard
4. William L. Hamilton
5. Gauthier Gidel

In Management Science and Operations Research

1. Gauthier Gidel
2. Simon Lacoste-Julien
3. Pascal Vincent
4. Avishek Joey Bose
5. Hugo Berard
6. William L. Hamilton

In Statistical Learning Theory

1. Simon Lacoste-Julien
2. Pascal Vincent
3. William L. Hamilton

In Algorithms & Complexity

1. Simon Lacoste-Julien
2. Pascal Vincent
3. William L. Hamilton
4. Gauthier Gidel

Citations in the corpus

• Online Adversarial Attacks (2021, methodology): “Secretary problems have also been applied to machine learning, via machine-learned advice which informs the online algorithm about the inputs before execution Antoniadis et al. [2020], Dütting et al. [2020]. Finally, other interesting secretary settings, in addition to the random order model, includ”