Learnable and Instance Robust Predictions for Online Matching, Flows, and Load Balancing

Published in European Symposium on Algorithms (ESA), 2021

This paper develops a new model for online algorithms with predictions focused on two aspects, learnability of the predictions and a new notion called instance robustness. This model is then applied to the online flow allocation problem in DAGs and online load balancing with restricted assignments.