i) One gets an improved approximation guarantee in case the machine-learned information is accurate;
ii) One does not lose too much in the approximation guarantee of the original algorithm in case the information is highly inaccurate.
In this talk, I will illustrate these concepts using the classical secretary problem, and discuss some extensions to other online selection problems such as online bipartite matching.
--------------------------
Join Zoom Meeting
https://zoom.us/j/5272788807?pwd=bmFVaUMyeURYNDJLT2kyaWVQNEdiUT09
Meeting ID: 527 278 8807
For people outside D1, please email skisfalu@mpi-inf.mpg.de if you wish to join.