Learning augmented algorithm

A learning-augmented algorithm is an algorithm that accepts, alongside its normal problem input, a prediction produced by a machine learning model or other external source, and uses that prediction to improve its performance beyond what a purely worst-case algorithm can guarantee. Rather than assuming no advance knowledge of the instance, the algorithm treats the prediction as untrusted advice about the input, an estimate of the optimal solution, or a forecast of future data, and folds it into its decisions. The framework is judged by three properties: consistency, meaning the algorithm performs close to optimal when the prediction is accurate; smoothness, meaning its performance degrades gracefully as the prediction gets worse; and robustness, meaning it still matches the guarantees of a classical algorithm even with no useful prediction at all. This lets designers combine the practical gains of machine-learned forecasting with the worst-case safety guarantees classical algorithm design normally provides.