Competitive strategies to use "warm start" algorithms with predictions

arXiv:2405.03661v1 Announce Type: cross
Abstract: 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 …

abstract algorithm algorithms arxiv cs.ds cs.lg instance prediction predictions solution strategies the algorithm type warm