When Switching Algorithms Helps: A Theoretical Study of Online Algorithm Selection
Denis Antipov, Carola Doerr · Proceedings of the Genetic and Evolutionary Computation Conference · 2026
Online algorithm selection (OAS) aims to adapt the optimization process to changes in the fitness landscape and is expected to outperform any single algorithm from a given portfolio. Although this expectation is supported by numerous empirical studies, there are currently no theoretical results proving that OAS can yield asymptotic speedups (apart from artificial examples for hyper-heuristics). Moreover, theory-based guidelines for when and how to switch between algorithms are largely missing.