Before revision:  Instance robustness formally ensures a prediction is robust to modest changes in the problem input . Further, the robustness model ensures two different predictions can be objectively compared, addressing a shortcoming in prior models. This paper establishes the existence of predictions which satisfy these properties. The paper considers online algorithms with predictions for a network flow allocation problem and the restricted assignment makespan minimization problem .
After revision:  Instance robustness formally ensures a prediction is robust to modest changes in the problem input , where the measure of the change may be problem specific. Instance robustness insists on a smooth degradation in performance as a function of the change. Ideally, the performance is never worse than worst-case bounds. This also allows predictions to be objectively compared. We design online algorithms with predictions for a network flow allocation problem and the restricted assignment makespan minimization problem .