Competitive strategies to use “warm start” algorithms with predictions
Avrim L. Blum, Vaidehi Srinivas · Society for Industrial and Applied Mathematics eBooks · 2025
We consider the problem of learning and using predictions for warm start algorithms with predictions. In this setting, an algorithm is given an instance of a problem, and a prediction of the solution. The runtime of the algorithm is bounded by the distance from the predicted solution to the true solution of the instance. Previous work has shown that when instances are drawn iid from some distribution, it is possible to learn an approximately optimal fixed prediction [DIL+21], and in the adversarial online case, it is possible to compete with the best fixed prediction in hindsight [KBTV22].