Learning-Augmented Algorithms

Learning-augmented algorithms (also known as algorithms with predictions) attempt to go beyond worst-case bounds of classic algorithms by accessing an oracle that offers possibly imperfect predictions. The oracle could be, e.g., a trained machine-learning model, which tries to predict a partial solution or a yet unknown portion of the input. The challenge is to use the oracle in a robust way, i.e., to retain the best classic worst-case guarantees while achieving optimal performance for accurate predictions.